HDU 5322 Hope ——NTT 分治 递推

发现可以推出递推式。（并不会）

然后化简一下，稍有常识的人都能看出这是一个NTT+分治的情况。

然而还有更巧妙的方法，直接化简一下递推就可以了。

太过巧妙，此处不表，建议大家找到那篇博客。

自行抄写

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

#define md 998244353

#define maxn 100005

int dp[maxn],fac[maxn],inv[maxn];

int ksm(int a,int b)

{

    int ret=1;

    for (;b;b>>=1,a=(ll)a*a%md) if (b&1) ret=(ll)ret*a%md;

    return ret;

}

int main()

{

    fac[0]=1;F(i,1,maxn-1)fac[i]=(ll)fac[i-1]*i%md;

    inv[maxn-1]=ksm(fac[maxn-1],md-2);

    D(i,maxn-2,0) inv[i]=(ll)inv[i+1]*(i+1)%md;

    int sum1=0,sum2=0,sum3=0,n;

    F(i,0,maxn-1)

    {

        if (!i) dp[i]=1;

        else dp[i]=(ll)fac[i-1]*(((ll)i*i%md*sum1%md+(ll)sum3-2LL*i*sum2%md)%md+md)%md;

        sum1=(sum1+1LL*dp[i]*inv[i])%md;

        sum2=(sum2+1LL*i*dp[i]%md*inv[i])%md;

        sum3=(sum3+1LL*i*i%md*dp[i]%md*inv[i])%md;

    }

    while (scanf("%d",&n)!=EOF) printf("%d\n",dp[n]);

}