题目描述
第二类斯特林数S（n，m）表示把n个不同元素划分成m个相同的集合中（不能有空集）的方案数。

给定n，对于所有的整数i∈[0,n]，你要求出S（n，i）

由于答案会非常大，所以你的输出需要对167772161（225×5+1，是一个质数）取模。

输入格式
一行一个正整数n，意义见题目描述。

输出格式
共一行n+1个非负整数。

你需要按顺序输出 S ( n , i )

输入输出样例
输入 #1 复制
3
输出 #1 复制
0 1 3 1
说明/提示
1⩽n⩽2×105。

首先要注意到167772161的原根是3。
然后再将第二类斯特林数的公式写出来，观察发现是个卷积形式。
于是用ntt就可以在nlogn时间内解决。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=8e5+1000;
const int p=167772161;
const int g=3;
int fi[maxn];
int a[maxn],b[maxn];
int fac[maxn],inv[maxn];

int mypow(int a,int b)
{
    if(b<0) return mypow(mypow(a,p-2),-b);
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%p;
    inv[n]=mypow(fac[n],p-2);
    for(int i=n-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%p;
}


void ntt(int *x,int len,int f)
{
    for(int i=0;i<len;i++)
        if(i<fi[i]) swap(x[i],x[fi[i]]);

    for(int i=1;i<len;i<<=1)
    {
        int r=i<<1;
        int wn=mypow(g,f*(p-1)/r);
        for(int j=0;j<len;j+=r)
        {
            int w=1;
            for(int k=0;k<i;k++)
            {
                int xx=x[j+k],yy=w*x[j+i+k]%p;
                x[j+k]=(xx+yy)%p;
                x[j+i+k]=((xx-yy)%p+p)%p;
                w=w*wn%p;
            }
        }
    }
    if(f==-1)
    {
        int invn=mypow(len,p-2);
        for(int i=0;i<len;i++)
            x[i]=x[i]*invn%p;
    }

}

void getntt(int n,int m)
{
    int len=1,cnt=0;
    while(len<=n+m) len<<=1,cnt++;
    for(int i=0;i<len;i++)
        fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));

    ntt(a,len,1);
    ntt(b,len,1);
    for(int i=0;i<len;i++)
        a[i]=a[i]*b[i]%p;
    ntt(a,len,-1);
}

signed main(void)
{
    int n;
    scanf("%lld",&n);
    init(n);
    for(int i=0;i<=n;i++)
    {
        if(i&1) a[i]=(-inv[i]+p)%p;
        else a[i]=inv[i];
        b[i]=mypow(i,n)*inv[i]%p;
    }
    getntt(n,n);
    for(int i=0;i<=n;i++)
        printf("%lld ",a[i]);

    return 0;

}