loj2058 「TJOI / HEOI2016」求和

推柿子

第二类斯特林数的容斥表达

fft卡精度就用ntt吧qwq。

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, lim=1, limcnt, rev[300005], inv[300005], a[300005], b[300005], jie[300005];

const int mod=998244353, gg=3, gi=332748118;

int ksm(int a, int b){

	int re=1;

	while(b){

		if(b&1)	re = (ll)re * a % mod;

		a = (ll)a * a % mod;

		b >>= 1;

	}

	return re;

}

void ntt(int a[], int opt){

    for(int i=0; i<lim; i++)

        if(i<rev[i])

            swap(a[i], a[rev[i]]);

    for(int i=2; i<=lim; i<<=1){

        int tmp=i>>1, wn=ksm(opt==1?gg:gi, (mod-1)/i);

        for(int j=0; j<lim; j+=i){

            int w=1;

            for(int k=0; k<tmp; k++){

                int tmp1=a[j+k], tmp2=(ll)w*a[j+k+tmp]%mod;

                a[j+k] = (tmp1 + tmp2) % mod;

                a[j+k+tmp] = (tmp1 - tmp2 + mod) % mod;

                w = (ll)w * wn % mod;

            }

        }

    }

    if(opt==-1){

        int inv=ksm(lim, mod-2);

        for(int i=0; i<lim; i++)

            a[i] = (ll)a[i] * inv % mod;

    }

}

int main(){

	cin>>n;

	while(lim<=n+n)	lim <<= 1, limcnt++;

	for(int i=0; i<lim; i++)

		rev[i] = (rev[i>>1]>>1) | ((i&1)<<(limcnt-1));

	int tmp=1, ans=0;

	inv[0] = inv[1] = jie[0] = jie[1] = 1;

	for(int i=2; i<lim; i++){

		jie[i] = (ll)jie[i-1] * i % mod;

		inv[i] = (ll)(mod-mod/i) * inv[mod%i] % mod;

	}

	for(int i=2; i<lim; i++)

		inv[i] = (ll)inv[i] * inv[i-1] % mod;

	for(int i=0; i<=n; i++){

		a[i] = (tmp*inv[i]+mod) % mod;

		tmp *= -1;

	}

	for(int i=0; i<=n; i++){

		if(i==0)	b[i] = 1;

		else if(i==1)	b[i] = n + 1;

		else

			b[i] = (ll)(ksm(i,n+1)-1+mod)%mod*ksm(i-1,mod-2)%mod*inv[i]%mod;

	}

	ntt(a, 1);

	ntt(b, 1);

	for(int i=0; i<lim; i++)

		a[i] = (ll)a[i] * b[i] % mod;

	ntt(a, -1);

	tmp = 1;

	for(int i=0; i<=n; i++){

		int qaq=(ll)tmp*jie[i]%mod;

		tmp = (ll)tmp * 2 % mod;

		qaq = (ll)qaq * a[i] % mod;

		ans = (ans + qaq) % mod;

	}

	cout<<ans<<endl;

	return 0;

}