【模板】第二类斯特林数·列

从通项公式入手好像不行了。

 

法一：

直接从定义入手：把n个球划分成m个等价类

假设等价类两两不同，最后除以m！

直接上EGF，A=∑1/i! x^i

A^m的i次项系数，再乘上i！再除以m！

 

法二：

从递推公式入手：$s(n,m)=s(n-1,m-1)+m*s(n-1,m)$

设OGF：$s_m(x)$是第m列二斯的OGF，则$s_m(x)=m*x*s_m(x)+x*s_{m-1}(x)$

接着迭代下去，得到分治NTT+求逆的式子，直接做即可

const int N=262144+5;
int n,m;
Poly divi(int l,int r){
    if(l==r){
        Poly ret;ret.resize(2);
        ret[0]=1;ret[1]=mod-l;
        return ret;
    }
    int mid=(l+r)>>1;
    Poly le=divi(l,mid),ri=divi(mid+1,r);
    return le*ri;
}
int main(){
    rd(n);rd(m);
    Poly A=divi(1,m);
    Poly B;B.resize(m+1);
    B[m]=1;
    A.resize(max(A.size(),n-m+1));
    A=B*(~A);
    A.resize(n+1);
    A.out();
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}