推柿子
第二类斯特林数的容斥表达
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;
}