推式子

那么就转化为一个卷积形式 。那么 。用 优化一下，就变为 了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 100,mod = 167772161;
int read() {int x;scanf("%d",&x);return x;}
int ksm(int a,int b) {
    int x = 1;for(;b;b>>=1,a=a*1ll*a%mod){
        if(b&1) x=x*1ll*a%mod;
    }return x;
} 
int f[N],g[N],r[N],fac[N],ifac[N],L,limit = 1;
void NTT(int *a,int type) {
    for(int i = 0;i < limit;i++)if(r[i]>i)swap(a[i],a[r[i]]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = ksm(3,(mod - 1)/(mid << 1));
        for(int i = 0;i < limit;i += (mid<<1)) {                
            for(int j = 0,w = 1;j < mid;j++,w = w*1ll*wn%mod) {
//                cout << a[i + j] <<" " <<a[i + j + mid] << endl;
                int x = a[i + j],y = 1ll * w * a[i + j + mid] % mod;
                a[i + j] = (x + y) % mod;a[i + j + mid] = (x - y + mod) % mod;
            }
        }
    }if(type == -1) {
        reverse(a + 1,a + limit);int Inv = ksm(limit,mod - 2);
        for(int i = 0;i < limit;i++) a[i] = a[i] * 1ll * Inv % mod;
    }
}
int main() {
    int n = read();fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = fac[i - 1] * 1ll * i % mod;
    ifac[n] = ksm(fac[n],mod - 2);
    for(int i = n - 1;i >= 0;i--) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % mod;
    for(int i = 0;i <= n;i++) {
        if(i & 1) f[i] = (-1ll * ifac[i] + mod) % mod;else f[i] = ifac[i];
        g[i] = ksm(i,n) * 1ll * ifac[i] % mod;
    }
    while(limit <= n + n) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) r[i] = (r[i>>1]>>1)|((i&1)<<L-1);
    NTT(f,1);NTT(g,1);for(int i = 0;i < limit;i++) f[i] = f[i] * 1ll * g[i] % mod;
    NTT(f,-1);for(int i = 0;i <= n;i++) printf("%d ",f[i]);printf("\n");return 0;
}