[HEOI2016/TJOI2016] 求和

推式子

\[ f(n)=\sum_{i=0}^n\sum_{j=0}^is(i,j)\times 2^j\times (j!)\\ =\sum_{i=0}^n\sum_{j=0}^ns(i,j)\times 2^j\times (j!)=\sum_{i=0}^n2^i\times (i!)\sum_{j=0}^n s(j,i) \]

注意到

\[ s(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^ic(m,i)(m-i)^n\\ =\sum_{i=0}^m\frac{(-1)^i\times (m-i)^n}{i!\times (m-i)!} \]

带入得

\[ f(n)=\sum_{i=0}^n2^i\times i!\sum_{j=0}^n\sum_{k=0}^i\frac{(-1)^k\times(i-k)^j}{k!\times (i-k)!}\\ =\sum_{i=0}^n2^i\times i!\sum_{k=0}^i\frac{(-1)^k}{k!}\frac{\sum_{j=0}^n(i-k)^j}{(i-k)!}\\ \]

注意，其中的\(0^0=1\)而非“未定义的操作”：离散、计数问题大都如此，可以参考。然后就是很显然的卷积。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

const int n=4e5+10;
const int mod=998244353;

inline int qpow(ll x,ll y) {
    int c=1;
    for(; y; y>>=1,x=x*x%mod) if(y&1) c=x*c%mod;
    return c;
}
int p,pl,rev[n];
inline void ntt_init(int sum) {
    for(p=1,pl=0; p<sum;) p<<=1,pl++;
    for(int i=0; i<p; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(pl-1));
}
inline void ntt(int*a,int tp) {
    for(int i=0; i<p; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int m=1; m<p; m<<=1) {
        ll wm=qpow(3,(mod-1)/(m<<1)); if(tp<0) wm=qpow(wm,mod-2);
        for(int i=0; i<p; i+=(m<<1)) { ll w=1,tmp;
            for(int j=0; j<m; ++j,w=w*wm%mod) {
                tmp=w*a[i+j+m]%mod;
                a[i+j+m]=(a[i+j]-tmp+mod)%mod;
                a[i+j]=(a[i+j]+tmp)%mod;
            }
        }
    }
    if(tp<0) {
        ll tmp=qpow(p,mod-2);
        for(int i=0; i<p; ++i) a[i]=tmp*a[i]%mod;
    }
}
int n,f[n],g[n];
ll fc[n],fv[n];

int main() {
    scanf("%d",&n);
    fc[0]=fc[1]=fv[0]=fv[1]=1;
    for(int i=2; i<=n; ++i) fv[i]=fv[mod%i]*(mod-mod/i)%mod;
    for(int i=2; i<=n; ++i) fv[i]=fv[i-1]*fv[i]%mod,fc[i]=fc[i-1]*i%mod;
    f[0]=1,f[1]=mod-1,g[0]=1,g[1]=n+1;
    for(int i=2; i<=n; ++i) {
        f[i]=fv[i]*((i&1)?mod-1:1)%mod;
        g[i]=fv[i]*((qpow(i,n+1)-1+mod)%mod)%mod*qpow(i-1,mod-2)%mod;
    }
    //for(int i=0; i<=n; ++i) printf("%d ",f[i]); printf("\n");
    //for(int i=0; i<=n; ++i) printf("%d ",g[i]); printf("\n");
    
    ntt_init(n+n+2);
    ntt(f,1); ntt(g,1);
    //for(int i=0; i<p; ++i) printf("%d ",f[i]); printf("\n");
    //for(int i=0; i<p; ++i) printf("%d ",g[i]); printf("\n");
    
    for(int i=0; i<p; ++i) f[i]=1ll*f[i]*g[i]%mod;
    ntt(f,-1); ll p=1,sum=0;
    for(int i=0; i<=n; ++i) {
        sum=(sum+p*fc[i]%mod*f[i]%mod)%mod;
        p=p*2%mod;
    }
    printf("%lld\n",sum);
    return 0;
}

写代码是别把p和mod弄混了……