Luogu5162 WD与积木（生成函数+多项式求逆）

时间：2023-03-09 01:22:09
Luogu5162 WD与积木（生成函数+多项式求逆）

　　显然的做法是求出斯特林数，但没有什么优化空间。

　　考虑一种暴力dp，即设f[i]为i块积木的所有方案层数之和，g[i]为i块积木的方案数。转移时枚举第一层是哪些积木，于是有f[i]=g[i]+ΣC(i,j)·f[i-j]，g[i]=ΣC(i,j)·g[i-j] (j=1~i)。

　　考虑优化 。我们发现这个转移非常像卷积。写成卷积形式，有f[i]=g[i]+Σi!·Σf[i-j]/j!/(i-j)!，g[i]=i!·Σg[i-j]/j!/(i-j)!。直接分治NTT即可。

　　诶是不是强行多了个log？考虑构造出生成函数。g比较简单，将该式写成g[i]/i!=Σg[i-j]/j!/(i-j)!，设g[i]/i!生成函数为G(x)，inv(i!)生成函数为H(x)，则有G(x)=G(x)·H(x)-G(x)+1，也即G(x)=1/(2-H(x))。f同样写成f[i]/i!=g[i]/i!+Σf[i-j]/j!/(i-j)!，则有F(x)=G(x)+F(x)·H(x)-F(x)-1，也即F(x)=G(x)·(G(x)-1)。多项式求逆即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define P 998244353

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,n,t,r[<<],f[<<],g[<<],h[<<],tmp[<<];

int ksm(int a,int k)

{

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int inv(int a){return ksm(a,P-);}

void DFT(int *a,int n,int g)

{

    for (int i=;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);

    for (int i=;i<=n;i<<=)

    {

        int wn=ksm(g,(P-)/i);

        for (int j=;j<n;j+=i)

        {

            int w=;

            for (int k=j;k<j+(i>>);k++,w=1ll*w*wn%P)

            {

                int x=a[k],y=1ll*w*a[k+(i>>)]%P;

                a[k]=(x+y)%P,a[k+(i>>)]=(x-y+P)%P;

            }

        }

    }

}

void mul(int *a,int *b,int n,int op)

{

    for (int i=;i<n;i++) r[i]=(r[i>>]>>)|(i&)*(n>>);

    DFT(a,n,),DFT(b,n,);

    if (op==) for (int i=;i<n;i++) a[i]=1ll*a[i]*b[i]%P;

    else for (int i=;i<n;i++) a[i]=1ll*a[i]*(P+-1ll*a[i]*b[i]%P)%P;

    DFT(a,n,inv());

    int t=inv(n);

    for (int i=;i<n;i++) a[i]=1ll*a[i]*t%P;

}

void getinv(int n)

{

    g[]=;

    for (int i=;i<=n;i<<=)

    {

        for (int j=i;j<(i<<);j++) tmp[j]=;

        for (int j=;j<i;j++) tmp[j]=h[j];

        mul(g,tmp,i<<,);

        for (int j=i;j<(i<<);j++) g[j]=;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();int t=;while (t<=(N<<)) t<<=;

    h[]=h[]=;for (int i=;i<=N;i++) h[i]=P-1ll*(P/i)*h[P%i]%P;

    for (int i=;i<=N;i++) h[i]=1ll*h[i]*h[i-]%P;

    for (int i=;i<=N;i++) h[i]=(P-h[i])%P;

    h[]=(h[]+)%P;

    getinv(t);

    for (int i=N+;i<t;i++) g[i]=;

    memcpy(f,g,sizeof(f));f[]--;if (f[]<) f[]+=P;

    mul(f,g,t,);DFT(g,t,inv());int u=inv(t);for (int i=;i<t;i++) g[i]=1ll*g[i]*u%P;

    while (T--)

    {

        n=read();

        printf("%d\n",1ll*f[n]*inv(g[n])%P);

    }

    return ;

}

相关文章