Cptraser/ 三月 6, 2019/ 2019.3/ 0 comments

指数型生成函数

定义指数型生成函数为:

    \[G(x) = a_0 + a_1x + a_2\frac{x^2}{2!} + a_3\frac{x^3}{3!} + a_4\frac{x^4}{4!} + \dots  = \sum\limits_{i = 0}^{\infty} a_i\frac{x^i}{i!}\]

F(x)=G(x)· G(x)=(\sum_{i=0}^{\infty}a_{i}\frac{x^{i}}{i!})(\sum_{i=0}^{\infty}a_{i}\frac{x^{i}}{i!})

最终得到:

    \[F(x)=\sum_{n=1}^{\infty}(\sum_{i=0}^{\infty} {n\choose i}a_{i}a_{n-i})\frac{x^{n}}{n!}\]

移动一下可以发现:

    \[\frac{F(n)}{n!}=\sum_{i=0}^{n}\frac{G(i)}{i!}\frac{G(n-i)}{(n-i)!}\]

然后就可以很方便地用多项式算法优化了。

题目大意

桌面上摆放着 m种魔术卡,共 n 张,第 i 种魔术卡数量为 a_i,魔术卡顺次摆放,形成一个长度为 n 的魔术序列,在魔术序列中,若两张相邻魔术卡的种类相同,则它们被称为一个魔术对。
两个魔术序列本质不同,当且仅当存在至少一个位置,使得两个魔术序列这个位置上的魔术卡的种类不同,求本质不同的恰好包含 k 个魔术对的魔术序列的数量,答案对 998244353 取模。

传送门

Solution

CJJ大仙秒了。

根据套路我们需要求出魔法对个数\geq k的方案数然后广义容斥。

定义f_{i,j}表示前i个颜色,分成j块的方案数,我们可以枚举i这个颜色分成了k块,然后转移:

    \[f_{i,j}=\sum_{k}f_{i-1,j-k}{a_{i}-1\choose k-1}{j\choose k}\]

{a_{i}-1\choose k-1}表示a_{i}分成k块的方案数,j\choose k表示k块插入到j中去的方案数。

其实{a_{i}-1\choose k-1}就是A_{i,k}(另一个多项式)

然后我们用分治NTT来加速指数型生成函数的卷积。

    \[\frac{f_{i,j}}{j!}=\sum_{k}\frac{f_{i-1,j-k}}{(j-k)!}\frac{A_{i,k}}{k!}\]

最后只要乘回一个阶乘即可。

所以最后用广义容斥求出答案:

    \[\sum_{i=k}^{n-1}(-1)^{i-k}{i\choose k}f_{m,n-i}\]

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> vc;
const int Mod=998244353,Maxn=4e5+5,G=3,InvG=332748118;

long long Ksm(long long x,long long y){
    long long res=1;for(;y;y>>=1,x=x*x%Mod)if(y&1)res=res*x%Mod;return res;
}

namespace Poly{
    int r[Maxn],wn[Maxn][2];
    void pre(int n){
        for(int i=1;i<=n;i++)r[i]=(r[i>>1]>>1)|((i&1)*(n>>1));
        for(int i=2;i<=n;i<<=1)wn[i][0]=Ksm(InvG,(Mod-1)/(i<<1)),wn[i][1]=Ksm(G,(Mod-1)/(i<<1));
    }
    void NTT(int *A,int Opt,int limit){
        for(int i=0;i<limit;i++)if(i<r[i])swap(A[i],A[r[i]]);
        for(int Mid=1;Mid<limit;Mid<<=1){
            for(int j=0;j<limit;j+=(Mid<<1)){
                long long w=1;
                for(int k=0;k<Mid;k++,w=(w*wn[Mid][Opt>0])%Mod){
                    int x=A[j+k],y=w*A[j+k+Mid]%Mod;
                    A[j+k]=(x+y)%Mod;
                    A[j+k+Mid]=(x-y+Mod)%Mod;
                }
            }
        }if(Opt<0)for(int i=0,inv=Ksm(limit,Mod-2);i<=limit;i++)A[i]=1ll*A[i]*inv%Mod;
    }
    vc operator*(const vc &A,const vc &B){
        int limit=1,n=A.size(),m=B.size();static vc C;
        static int a[1<<18],b[1<<18];
        for(;limit<n+m-1;limit<<=1);pre(limit);
        for(int i=0;i<n;i++)a[i]=A[i];
        for(int i=0;i<m;i++)b[i]=B[i];
        for(int i=n;i<limit;i++)a[i]=0;
        for(int i=m;i<limit;i++)b[i]=0;
        NTT(a,1,limit),NTT(b,1,limit);
        for(int i=0;i<limit;i++)a[i]=1ll*a[i]*b[i]%Mod;NTT(a,-1,limit);
        C.clear();for(int i=0;i<n+m-1;i++)C.push_back(a[i]);
        return C;
    }
};
using namespace Poly;

long long Ans;
int N,M,K,Inv[Maxn],Fac[Maxn],A[Maxn],f[Maxn];
vc p[Maxn],F;
int C(int x,int y){
    if(x<y)return 0;return 1ll*Fac[x]*Inv[y]%Mod*Inv[x-y]%Mod;
}
#define Mid ((L+R)>>1)
vc Solve(int L,int R){
    if(L==R)return p[L];return Solve(L,Mid)*Solve(Mid+1,R);
}
#undef Mid
int main()
{
    scanf("%d%d%d",&M,&N,&K),Fac[0]=Fac[1]=1;
    for(int i=2;i<=N;i++)Fac[i]=1ll*Fac[i-1]*i%Mod;
    for(int i=0;i<=N;i++)Inv[i]=Ksm(Fac[i],Mod-2);
    for(int i=1;i<=M;i++)scanf("%d",&A[i]);
    for(int i=1;i<=M;i++){
        p[i].push_back(0);for(int j=1;j<=A[i];j++)p[i].push_back(1ll*C(A[i]-1,j-1)*Inv[j]%Mod);
    }F=Solve(1,M);
    for(int i=0;i<N;i++)f[i]=1ll*F[N-i]*Fac[N-i]%Mod;
    for(int i=K;i<=N;i++){
        (Ans+=1ll*((i-K)&1?Mod-1:1)*C(i,K)%Mod*f[i]%Mod)%=Mod;
    }printf("%lld",Ans);
}

参考文献

指数生成函数小练
指数型生成函数 及 多项式求ln
ZigZagK大佬的博客

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*