题解：AT_wtf22_day2_d Cat Jumps

· · 题解

第三次被模拟赛考了忍不了了来发一篇。

将所有正的互相区分，最后再乘 \prod\frac 1{occ_i!}。

钦定若干位置形成前缀和为 0，最终做二项式反演，有 G_k=\sum_{i\ge k}\binom{i-1}{k-1}F_i，其中 G_k 表示钦定了 k 个区间的方案数，F 为答案。令 k 个区间中每个区间的正的集合是 S_i，则方案数为 \prod_{i=1}^k\prod_{j=0}^{|S_i|-1}((\sum_{v\in S_i}v)+|S_i|-j)。拆开 (sum+1)(sum+2)\cdots(sum+k)，转化为每个 i 选出边 to_i，边权为 a_{to_i}+[to_i\leq i]。

这样形成内向基环树森林，算出有 k 个连通块方案数 g_k 时再用第二类斯特林数算到 G 上，有 g_xS_2(x,y)\to G_y。考虑算 G_k 可以钦定环做计数，假设钦定了 x 个环贡献为 h_x，有 h_x=\sum_{i\ge x}\binom{x}{i}g_i。算 h_x 考虑将不在环上的直接乘上所有出边边权和，否则算一个环的贡献系数相乘。

将环边边权拆为 a_v+[u\ge v]=(a_v+1)-[u<v]，这样转化为若干递增链，链头贡献 (a_u+1)，后面接着一堆 -1 的边。dp 计算当前链的个数。dp\to h 是用第一类斯特林数，即 dp_{n,x}S_1(x,y)\to h_y。

时间复杂度 \mathcal O(n^2)。

int n,a[maxn],ifac[maxn],fac[maxn];
int S2[maxn][maxn],S1[maxn][maxn],C[maxn][maxn];
void init(){
    const int N=5000;
    fac[0]=ifac[0]=1;
    F(i,1,N)fac[i]=1ll*fac[i-1]*i%mod,ifac[i]=qpow(fac[i],mod-2);
    S1[0][0]=S2[0][0]=1;
    F(i,0,N)C[i][0]=1;
    F(i,1,N)F(j,1,i)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
    F(i,1,N)F(j,1,i)S1[i][j]=add(S1[i-1][j-1],1ll*(i-1)*S1[i-1][j]%mod);
    F(i,1,N)F(j,1,i)S2[i][j]=add(S2[i-1][j-1],1ll*j*S2[i-1][j]%mod);
}
int dp[maxn][maxn];
int ans[maxn],vis[maxn],f[maxn],sum,F[maxn];
void solve(){
    cin>>n,init();
    F(i,1,n)cin>>a[i],inc(sum,a[i]);
    dp[0][0]=1;
    F(i,1,n)F(j,0,i-1){
        const int val=dp[i-1][j];if(!val)continue;
        inc(dp[i][j+1],1ll*val*(a[i]+1)%mod);
        inc(dp[i][j],1ll*val*(sum+i-j)%mod);
    }
    F(i,0,n)F(j,0,i)inc(f[j],1ll*dp[n][i]*S1[i][j]%mod);
    dF(i,n,1)F(j,i+1,n)dec(f[i],1ll*f[j]*C[j][i]%mod);
    F(i,1,n)F(j,1,i)inc(F[j],1ll*f[i]*S2[i][j]%mod);
    dF(i,n,1){
        ans[i]=1ll*F[i]*fac[i]%mod;
        F(j,i+1,n)dec(ans[i],1ll*C[j-1][i-1]*ans[j]%mod);
    }
    int coef=1;
    F(i,1,n)++vis[a[i]];
    F(i,1,n)coef=1ll*ifac[vis[a[i]]]*coef%mod,vis[a[i]]=0;
    F(i,1,n)ans[i]=1ll*ans[i]*coef%mod;
    F(i,1,n)cout<<ans[i]<<' ';cout<<'\n';
}