AT_wtf22_day2_d Cat Jumps 題解

AT_wtf22_day2_d Cat Jumps

好牛的數(shù)學(xué)題！

首先將所有 \(a_i\) 看成有相對順序的，然后最后將答案除以每個數(shù)出現(xiàn)次數(shù)的階乘。（注意 \(-1\) 之間仍然沒有相對順序）

然后因為是要求恰好 \(k\) 個硬幣，我們可以求欽定 \(k\) 個硬幣的方案，再使用二項式反演即可求得恰好的方案。一個序列是恰好獲得 \(k\) 個硬幣的，相當(dāng)于可以將序列劃分為 \(k\) 段，滿足每一段都是和為 \(0\) 的極小連續(xù)段，即不能再劃分下去。

設(shè) \(f_k\) 表示欽定 \(k\) 個硬幣的答案，就是將序列劃分為了 \(k\) 段滿足每一段的和為 \(0\)，但不用滿足每一段都是極小的。于是我們可以枚舉將 \(n\) 個數(shù)劃分為 \(k\) 個集合的方案，那么對于一個集合 \(S\)，相當(dāng)于把集合 \(S\) 中的 \(a_i\) 劃分為了一段。設(shè) \(sum = \sum\limits_{i\in S}a_i\)，這一段中就有 \(sum\) 個 \(-1\)，于是這一段的方案數(shù)為 \((sum+1)(sum+2)\ldots(sum+|S|)\)。這一個劃分方案的貢獻為所有段的方案數(shù)的乘積再乘上 \(k!\)。

注意最后二項式反演時容斥系數(shù)為 \((-1)^{j-i} {j-1\choose i-1}\)。這個做法復(fù)雜度為 \(\mathcal{O}(B_nn)\)，其中 \(B_n\) 表示貝爾數(shù)，即 \(n\) 個數(shù)的集合劃分方案，也等于 \(\sum\limits_{i=0}^n{n\brace i}\)。

繼續(xù)優(yōu)化，考慮這個式子的組合意義，相當(dāng)于一個完全圖，\(i\) 到 \(j\) 有邊權(quán)為 \(a_j+[j\le i]\) 的邊，一種劃分方案的貢獻為每個點向同一個集合內(nèi)的其中一個點連邊，所有連邊方案的邊權(quán)的乘積之和。因為一個集合內(nèi)編號第 \(i\) 小的點向集合內(nèi)所有點連邊的邊權(quán)和為 \(sum+i\)。

那么最終連出來的圖是一個內(nèi)向基環(huán)樹森林，假設(shè)每個點可以向任意點連邊，設(shè) \(g_k\) 表示最終有 \(k\) 個基環(huán)樹的方案，那么一個 \(g_i\) 對 \(f_j\) 的貢獻為將這 \(i\) 個基環(huán)樹劃分為 \(j\) 個集合的方案數(shù)，即 \(i\brace j\)。所以求出 \(g_i\) 后就能通過 \(f_i = \sum\limits_{j=i}^n g_j{j\brace i}\) 來求出 \(f_i\)。

現(xiàn)在考慮求 \(g_k\)，我們可以欽定有多少個環(huán)，設(shè)欽定有 \(k\) 個環(huán)的所有圖的權(quán)值和為 \(h_k\)，對 \(h\) 進行一次二項式反演即可得到 \(g\)。現(xiàn)在假設(shè)我們欽定了 \(k\) 個環(huán)，那么環(huán)外的點就可以向任意點連邊，所以一個環(huán)外的點 \(x\) 的貢獻為 \(x+\sum\limits_{i=1}^na_i\)。環(huán)上的邊權(quán)仍然是 \(a_j+[j\le i]\)，我們可以把這個式子寫成 \((a_j+1)-[j>i]\)。

考慮組合意義，因為是所有邊權(quán)乘起來，所以相當(dāng)于在每個 \((a_j+1)-[j>i]\) 的式子中選擇其中一項。那么對于一段選擇了 \(-1\) 的連續(xù)段，就對應(yīng)了一條編號遞增的鏈。換句話說，如果選擇了若干條編號遞增的鏈，就有每條鏈的鏈頭 \(j\) 的貢獻為 \(a_j\)，其余點的貢獻為 \(-1\)，然后再將這些鏈拼成 \(k\) 個環(huán)。假設(shè)我們求出了選擇 \(i\) 條鏈的權(quán)值和，那么拼成 \(j\) 個環(huán)的方案數(shù)相當(dāng)于將 \(i\) 條鏈劃分為 \(j\) 個集合，每個集合 \(S\) 的貢獻為 \((|S|-1)!\)，可以發(fā)現(xiàn)這就是 \({i\brack j}\)。于是我們求出選擇 \(k\) 條鏈的權(quán)值和之后，乘第一類斯特林?jǐn)?shù)即可得到 \(h_k\)。

現(xiàn)在考慮求選擇 \(k\) 條鏈的權(quán)值和。設(shè) \(dp_{i,j}\) 表示編號前 \(i\) 的點，拼成 \(j\) 條鏈的權(quán)值和，那么對于第 \(i\) 個點分三種情況討論：

• 單獨成一條鏈，鏈頭貢獻為 \(a_i\)：\(dp_{i,j}\larr dp_{i-1,j-1}a_i\)
• 接在某一條鏈的后面，貢獻為 \(-1\)：\(dp_{i,j}\larr dp_{i-1,j}\times (-j)\)
• 放在環(huán)外，貢獻為 \(i+\sum\limits_{j=1}^n a_j\)：\(dp_{i,j}\larr dp_{i-1,j}(i+\sum\limits_{j=1}^n a_j)\)。

于是整個問題可以在 \(\mathcal{O}(n^2)\) 內(nèi)求出。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const ll N = 5005,mod = 998244353;
int tong[N],n;ll a[N],s;
ll fac[N],inv[N],f[N],g[N],S1[N][N],S2[N][N],C[N][N],dp[N][N],d = 1;
map<int,int> mp;
void init()
{
    dp[0][0] = S1[0][0] = S2[0][0] = C[0][0] = fac[0] = inv[0] = inv[1] = 1;
    for(int i = 2;i <= n;i++)inv[i] = (mod-mod/i)*inv[mod%i]%mod;
    for(int i = 1;i <= n;i++)fac[i] = fac[i-1]*i%mod;
    for(int i = 1;i <= n;i++)for(int j = C[i][0] = 1;j <= i;j++)
    {
        C[i][j] = (C[i-1][j-1]+C[i-1][j])%mod;
        S1[i][j] = (S1[i-1][j-1]+S1[i-1][j]*(i-1))%mod;
        S2[i][j] = (S2[i-1][j-1]+S2[i-1][j]*j)%mod;
    }
}
char buf[1<<21],*p1,*p2;
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n = rd();init();
    for(int i = 1;i <= n;i++)d = d*inv[++mp[a[i] = rd()]]%mod,(s += a[i]) %= mod;
    for(int i = 1;i <= n;i++)for(int j = 0;j <= i;j++)
        dp[i][j] = ((j?dp[i-1][j-1]*(a[i]+1):0)+dp[i-1][j]*(s+i-j))%mod;
    for(int i = 0;i <= n;i++)for(int j = i;j <= n;j++)
        (g[i] += dp[n][j]*S1[j][i]) %= mod;
    for(int i = n;~i;i--)for(int j = i+1;j <= n;j++)
        (g[i] -= g[j]*C[j][i]) %= mod;
    for(int i = 1;i <= n;f[i] = f[i]*fac[i]%mod,i++)for(int j = i;j <= n;j++)
        (f[i] += g[j]*S2[j][i]) %= mod;
    for(int i = n;i;i--)for(int j = i+1;j <= n;j++)
        (f[i] -= f[j]*C[j-1][i-1]) %= mod;
    for(int i = 1;i <= n;i++)printf("%lld\n",(f[i]+mod)*d%mod);
    return 0;
}