题面

题解

复杂度比较迷啊……

以下以\(n\)表示颜色总数，\(m\)表示总的卡牌数

严格\(k\)对比较难算，我们考虑容斥

首先有\(i\)对就代表整个序列被分成了\(m-i\)块互不相同的部分，那么我们从被分成了多少块这个角度来考虑

设\(f_{i,j}\)表示考虑前\(i\)中颜色被分成了\(j\)块的方案（这里的\(j\)块不一定满足相邻两块颜色不同），那么转移就是

\[f_{i,j}=\sum_k f_{i-1,j-k}{a_i-1\choose k-1}{j\choose k}\]

也就是相当于我们枚举一下第\(i\)种颜色分成了\(k\)块，那么方案数是\({a_i-1\choose k-1}\)，然后一共\({j\choose k}\)表示\(k\)块和\(j-k\)块之间交叉放置的方案数

初值显然为

\[f_{1,i}={a_1-1\choose i-1}\]

如果我们记

\[F_i=\sum_{i=0}^\infty {a_i-1\choose i-1}{x^i\over i!}\]

那么发现答案最终的\(f_n\)的指数型生成函数就是

\[\prod_{i=1}^nF_i\]

分治\(NTT\)即可

最后求出了\(f_n\)，那么\(f_{n,i}\)表示\(n\)种颜色分成\(i\)块的方案数，即有\(m-i\)个魔法对的方案数

我们记\(g_i=f_{n,m-i}\)，那么通过容斥原理可得最终的答案为

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

复杂度的话，因为一层\(\sum a_i=m\)，所以分治的时候一层里的复杂度为\(O(n\log n)\)，总共\(O(\log n)\)层，复杂度为\(O(n\log^2n)\)

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=(1<<18)+5,P=998244353;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int r[21][N],rt[2][N],inv[N],fac[N],ifac[N],lg[N],ilim[21];int lim,d,n,m,k;inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}void Pre(){    fp(d,0,18){        fp(i,1,(1<
      
       >1]>>1)|((i&1)<<(d-1));        lg[1<
       
        <
        
         >1,i=1,x,y;i<262144;i<<=1,t>>=1){        x=ksm(3,t),y=ksm(332748118,t),rt[0][i]=rt[1][i]=1;        fp(k,1,i-1)            rt[1][i+k]=mul(rt[1][i+k-1],x),            rt[0][i+k]=mul(rt[0][i+k-1],y);    }}inline void init(R int len){lim=1,d=0;while(lim
         
          <<=1,++d;}void NTT(int *A,int ty){ fp(i,0,lim-1)if(i
          
           >1; solve(p,l,mid),solve(p+1,mid+1,r); static int A[N],B[N];init(deg[p]+deg[p+1]+1); fp(i,0,deg[p])A[i]=D[p][i];fp(i,deg[p]+1,lim-1)A[i]=0; fp(i,0,deg[p+1])B[i]=D[p+1][i];fp(i,deg[p+1]+1,lim-1)B[i]=0; NTT(A,1),NTT(B,1); fp(i,0,lim-1)A[i]=mul(A[i],B[i]); NTT(A,0); deg[p]+=deg[p+1]; fp(i,0,deg[p])D[p][i]=A[i]; fp(i,deg[p]+1,lim-1)D[p][i]=0;}int f[N],res;int main(){// freopen("testdata.in","r",stdin); n=read(),m=read(),k=read(),Pre(); fp(i,1,n)a[i]=read(); solve(1,1,n); fp(i,0,m-1)f[i]=mul(fac[m-i],D[1][m-i]); fp(i,k,m)res=add(res,((i-k)&1?P-1ll:1ll)*f[i]%P*C(i,k)%P); printf("%d\n",res); return 0;}