题解：P10005 [集训队互测 2023] 基础寄术练习题

好牛的计数题。

题意：很简单了，不再赘述。

做法：

首先看到这个前缀和的乘积的倒数太难算了，一般来说肯定是考虑拆成 \(a\) 怎么样算一下，经过一定的手玩以后会发现 \(\sum\prod\limits_{i}\frac{1}{s_i}=\prod\frac1{a_i}\)，但是我完全不知道怎么证明，然后点开了题解。

这里需要一个非常牛的转化，我们考虑现在有 \(n\) 种颜色的球，每种球分别有 \(a_i\) 个，我们钦定每种球最后一个出现位置的顺序并按这个顺序加入，那么合法的概率是：

\[\prod_{i=1}^n\frac{a_i(s_i-1)!}{s_i!} = \prod_{i=1}^n\frac{a_i}{s_i} \]

解释一下，我们只用保证第 \(i\) 个球加进去时，最后一个球是第 \(i\) 种即可，所以概率是上面这个。

同时，所有的顺序都可以，概率总和为 \(1\)，就会有:

\[\prod_{i=1}^na_i(\sum\prod_{i=1}^n\frac1{s_i}) = 1 \]

所以上面那个结论就证明了。

那么对于 \(k=1\)，直接 dp 就可以了，复杂度 \(O(n^2)\)。

---

接下来考虑 \(k=2\)，即我们要对于第一个是 \(a_i\) 的概率额外乘上 \(a_i\)，那我们肯定先枚举 \(a_i\)，考虑序列合法的概率再乘上贡献，这里先算概率，贡献很好算。

注意到此时我们要求 \(a_1\) 一定是结束位置最早的，所以我们这里考虑容斥，令 \(S\) 集合中的元素在 \(a_1\) 之前就已经被放完了，其他的随意，那么此时的方案数为：

\[\binom{\sum s_i}{s_1,s_2,\cdots s_k}\binom{\sum{s_i} + a_1 - 1}{a_1-1}\binom{\sum a_i}{\sum s_i+a_1} \]

解释一下，第一个是分配 \(S\) 内部的顺序，第二个是令 \(a_1\) 和 \(S\) 一起放，这时 \(a_1\) 必须在最后放一个，第三个就是所有数一起排。

把上面这个东西展开整理，可以得到：

\[\binom{\sum a_i}{a_1,a_2,\cdots a_n}\frac{a_1}{\sum s_i+a_1} \]

因为我们求的是概率，所以把前面的方案数会除掉。然后再乘上容斥系数。

那么对于所有的 \(S\)，贡献为：

\[\sum a_1\prod_{i=1}^n\frac{1}{a_i}\sum_{S}\frac{a_1}{\sum s_i+a_1}(-1)^{|S|} \]

我们用 dp 计算这个东西，看看我们需要什么，只有 \(\sum s_i+a_1\) 无法单独计算，还有 \(a_1\) 会有额外贡献，所以我们 dp 中就只需要记录选了多少个数，\(\sum_{}s_i+a_1\) 还有 \(a_1\) 选没选定就可以，转移时考虑不选，选成 \(a_1\)，选入 \(S\)，选入 \(\bar S\) 即可，复杂度 \(O(n^4)\)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n, m, k, mod, dp[maxn][maxn], inv[maxn * maxn];
void prepare() {inv[0] = inv[1] = 1;for (int i = 2; i <= n * m; i++)inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}
void solve1() {dp[0][0] = 1;for (int i = 1; i <= m; i++)for (int j = 0; j <= n; j++)dp[i][j] = (dp[i - 1][j] + 1ll * dp[i - 1][j - 1] * inv[i] % mod) % mod;cout << dp[m][n] << endl;
}
int f[2][maxn][maxn * maxn][2], lim[maxn];
void solve2() {int cur = 0;f[0][0][0][0] = 1;for (int i = 1; i <= m; i++)lim[i] = (i > n ? lim[i - 1] + n : lim[i - 1] + i);for (int i = 1; i <= m; i++) {cur ^= 1; memset(f[cur], 0, sizeof(f[cur]));for (int j = 0; j <= n; j++) {for (int k = 0; k <= lim[i]; k++) {// 不选f[cur][j][k][0] = f[cur ^ 1][j][k][0], f[cur][j][k][1] = f[cur ^ 1][j][k][1];// 选定为 a1if(k >= i && j)f[cur][j][k][1] = (f[cur][j][k][1] + 1ll * f[cur ^ 1][j - 1][k - i][0] * i % mod) % mod;// 选为 Sif(k >= i && j)f[cur][j][k][0] = (f[cur][j][k][0] - 1ll * f[cur ^ 1][j - 1][k - i][0] * inv[i] % mod + mod) % mod,f[cur][j][k][1] = (f[cur][j][k][1] - 1ll * f[cur ^ 1][j - 1][k - i][1] * inv[i] % mod + mod) % mod;// 选入S补if(j)f[cur][j][k][0] = (f[cur][j][k][0] + 1ll * f[cur ^ 1][j - 1][k][0] * inv[i] % mod) % mod,f[cur][j][k][1] = (f[cur][j][k][1] + 1ll * f[cur ^ 1][j - 1][k][1] * inv[i] % mod) % mod;}}//	cout << f[cur][1][2][1] << endl;}int ans = 0;for (int i = 1; i <= n * m; i++)ans = (ans + 1ll * f[cur][n][i][1] * inv[i] % mod) % mod;cout << ans << endl;
}
signed main() {cin >> n >> m >> k >> mod;prepare();if(k == 1) solve1();elsesolve2();return 0;
}