关原幽

首先给颜色打标签，最后撕掉就好了。

首先考虑想直接枚举

k

表示分出

k

段的方案数，但是发现有个问题就是很难保证中间不变成 0，于是考虑二项式反演一下就把恰好丢掉了（注意这里选区间使用的是区间端点所以容斥系数稍微有点区别），中间就直接插板。

然后就是这个题最鬼的一步，考虑这样的话因为分段需要枚举十分不优，我们需要想个听上去有道理的办法将贡献分开。

那么考虑对于一个大小为

A_i

的点，点

j

可以插在他的空隙中，也就是

A_i+1

，不过有一个空隙是和别人共享的所以干脆认为是

A_i

，然后对于他前面的点也就是当

i<j

的时候，前面的点已经插入了，空隙会多一个变成

A_i+[i<j]

，然后这样的话因为每个段都取了前面那个空隙而没取后面那个，所以需要在整体式子上在加一，考虑直接加到不等式上，那么点

i

最后贡献给点

j

的就是

A_i+[i\leqslant j]

，而显然每个点的权值也就是这些数加起来。

用乘法分配律把他拆开就变成了对于每个点

i

挑一个

j

并把

j

贡献给

i

的权值乘起来，把这个东西视作完全图的邻接矩阵，那么这个事情就是在其中求解基环树森林的权值和。

假设我们知道有

k

棵基环树的时候权值和是多少，那么我们显然可以用第二类斯特林数组出分

j

段的权值和是多少，而我们很难限制出恰好

k

棵基环树，所以变成至少

k

棵基环树再用这个东西二项式反演一次。

但是这个还是很难求，我们考虑环外点的权值是固定的，而环内点的权值却并非，我们考虑再乘法分配律一下，将环拆为若干单调的链，因为链单调所以链中非链头的点附加值确定存在，而链头附加值存不存在都无所谓干脆因为使用的是本来的权值所以没问题。

然后问题就是如何把链拼起来，容易发现这就是第一类斯特林数的定义，一步一步代回去便能得到答案。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=998244353;
int power(int x,int y=P-2){
   if(!y)return 1;
   int tmp=power(x,y>>1);
   if(y&1)return tmp*tmp%P*x%P;
   return tmp*tmp%P;
}
int n;
int A[5005];
int fac[5005];
int invfac[5005];
int S1[5005][5005];
int S2[5005][5005];
int C(int n,int m){
   return fac[n]*invfac[m]%P*invfac[n-m]%P;
}
int dp[5005][5005];
int h[5005];
int g[5005];
int f[5005];
int ans[5005];
int SUM;
int mul=1;
signed main(){
   scanf("%lld",&n);
   for(int i=1;i<=n;i++){
      scanf("%lld",&A[i]);
      SUM+=A[i];
      if(SUM>=P)SUM-=P;
   }
   sort(A+1,A+1+n);
   fac[0]=1;
   for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%P;
   invfac[n]=power(fac[n]);
   for(int i=n;i>=1;i--)invfac[i-1]=invfac[i]*i%P;
   int num=1;
   for(int i=2;i<=n;i++){
      if(A[i] xor A[i-1]){
         mul=mul*invfac[num]%P;
         num=0;
      }
      num++;
   }
   mul=mul*invfac[num]%P;
   S2[0][0]=1;
   for(int i=1;i<=n;i++){
      for(int k=1;k<=i;k++){
         S2[i][k]=S2[i-1][k-1]+k*S2[i-1][k];
         S2[i][k]%=P;
      }
   }
   S1[0][0]=1;
   for(int i=1;i<=n;i++){
      for(int k=1;k<=i;k++){
         S1[i][k]=S1[i-1][k]*(i-1)+S1[i-1][k-1];
         S1[i][k]%=P;
      }
   }
   dp[0][0]=1;
   for(int i=1;i<=n;i++){
      for(int j=0;j<=i;j++){
         dp[i][j]=dp[i-1][j]*(i+SUM)+dp[i-1][j]*(-1)*j;
         if(j)dp[i][j]+=dp[i-1][j-1]*(A[i]+1);
         dp[i][j]=(dp[i][j]%P+P)%P;
      }
   }
   for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j++){
         h[i]+=dp[n][j]*S1[j][i];
         h[i]%=P;
      }
   }
   for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j++){//
         int f=1;
         if((j-i)&1)f=-1;
         g[i]+=h[j]*f*C(j,i);
         g[i]=(g[i]%P+P)%P;
      }
   }
   for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j++){
         f[i]+=g[j]*S2[j][i];
         // if(i==2){
         //    printf("%lld*%lld\n",g[j],S2[j][i]);
         // }
         f[i]%=P;
      }
   }
   // printf("%lld %lld\n",f[1],f[2]);
   for(int i=1;i<=n;i++)f[i]=f[i]*fac[i]%P;
   // f[2]=12;
   // f[1]=12,f[2]=8;
   for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j++){//
         int fl=1;
         if((j-i)&1)fl=-1;
         ans[i]+=fl*f[j]*C(j-1,i-1);
         ans[i]=(ans[i]%P+P)%P;
      }
   }
   for(int i=1;i<=n;i++){
      printf("%lld\n",ans[i]*mul%P);
   }
   // puts("");
   return 0;
}//

文章操作

相关推荐

评论

关原幽