\(\text{P10005 [集训队互测 2023] 基础寄术练习题 题解}\)
有点人类智慧了说实在的。
先考虑看上去较为简单的 \(k=1\)，要求的就是序列前缀和的积的倒数。直接想去拆开来是不好做的，没有常见的等式形式满足这个东西，于是考虑组合意义。前缀和的积这个形式太难搞了，能否用一个模型转化掉？这个前缀和之积的形式很像树上拓扑序的式子：每次钦定根节点在首位，概率就是 \(\frac 1{siz}\)，并且概率也能不断向下迭代构成 \(\frac{1}{\prod siz_i}\) 的形式，因为去掉根的限制后都是互不相关的。那么将这个意义转化到序列上：相当于是有一个序列，值为 \(i\) 的元素有 \(a_i\) 个，要求元素 \(i\) 最后一次出现位置小于元素 \(i+1\) 最后一次出现位置。这个东西的概率从后往前考虑最后一次的取值显然是 \(\prod\frac{a_i}{s_i}\)。由于每种序列事实上与每种 \(a_i\) 是唯一对应的，这个东西就是考虑序列每种元素实际上的最终取值位置记录在 \(a\) 中，因此有 \(\sum_a\prod\frac{a_i}{s_i}=1\)。这样一来 \(\sum\prod\frac 1{s_i}=\sum\prod\frac 1{a_i}\)，那么设计 dp 求出在值域 \([1,m]\)，选出 \(n\) 个元素，对于元素 \(i\) 权值是 \(\frac 1i\) 的权值之和即可，这是背包 dp 的板子题。
对于 \(k=2\)，依然沿用之前的方法，看上去给每个答案 \(\times a_1\) 即可，但是不要忽略此时 \(a_1\) 最后的出现位置要最小的限制。我们计算排列合法的概率，直接处理这个限制是困难的，考虑容斥，钦定集合 \(B\) 内的元素最后一次出现位置是小于 \(a_1\) 的，那么我们依次插入元素，对应的方案数就是：
其中 \(b_i\) 是 \(B\) 内元素在序列中个数，\(c_i\) 是非 \(B\) 内元素且非 \(a_1\) 元素在序列中个数，\(S_B=\sum b_i\)。
然后求概率就除以 \(\frac{(\sum a)!}{\prod a_i}\)，贡献就是 \(\frac{a_1}{S_B+a_1}\)，乘上容斥系数 \((-1)^B\) 即可。这个东西是容易设计 dp 的：设 \(dp_{i,j,s,0/1}\) 表示前 \(i\) 个数中选了 \(j\) 个元素在 \(a\) 中，\(S_B+a_1=s\)，有没有钦定 \(a_1\) 时的系数，然后就做完了。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105, M = 1e4 + 5;
int n, m, k, p;
int inv[M];
inline void add(int &x, int y) {x = x + y >= p ? x + y - p : x + y;
}
namespace s1 {int dp[N];int main() {dp[0] = 1;for (int i = 1; i <= m; i++)for (int j = n; j; --j)add(dp[j], 1ll * dp[j - 1] * inv[i] % p);cout << dp[n] << '\n';return 0;}
}
namespace s2 {int dp[2][N][M][2];int main() {int u = 0;dp[0][0][0][0] = 1;for (int i = 1; i <= m; i++) {u ^= 1;for (int j = 0; j < N; j++)for (int t = 0; t < M; t++)dp[u][j][t][0] = dp[u][j][t][1] = 0;for (int j = 0; j < n; j++)for (int s = 0; s < M; s++)for (int r = 0; r < 2; r++) {int w = dp[u ^ 1][j][s][r];if (!w) continue;add(dp[u][j][s][r], w);add(dp[u][j + 1][s][r], 1ll * inv[i] * w % p);add(dp[u][j + 1][s + i][r], 1ll * (p - inv[i]) * w % p);if (!r) add(dp[u][j][s + i][1], 1ll * i * w % p);}}int ans = 0;for (int s = 0; s < M; s++) add(ans, 1ll * dp[u][n - 1][s][1] * inv[s] % p);cout << ans << '\n';return 0;}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m >> k >> p;inv[1] = 1;for (int i = 2; i < M; i++) inv[i] = 1ll * (p - p / i) * inv[p % i] % p;if (k == 1) return s1::main();return s2::main();
}