[组合计数] [容斥] [转化] P10005 [集训队互测 2023] 基础寄术练习题
_Cheems
·
·
题解
这题很牛，关键转化赛时想到了，但认为太魔怔了就没继续想下去。
k=1
联想除以连乘有什么可能的转化，发现和树的拓扑序计数有所联系，同时也容易处理前缀和这一要素。只需构造大小分别为 a_i 的菊花，然后按顺序将根连起来即可。
可以放在拓扑序列上对其简化，最终版本为：考虑有 n 种不同颜色的球，分别有 a_1\dots a_n 个，考虑依次插入每种颜色的球，则 i 插入时在序列末尾的概率为 \frac {a_i}{s_i}，因此记 r_i 为颜色 i 最右侧位置，则满足 r_1<r_2\dots <r_n 的排列占总排列个数的比例，即为 \frac {\prod a_i}{\prod s_i}，记作 g_P。
在 a_1\dots a_n 在集合意义下（排序后）相同的情况下，任意排列都会唯一贡献给一种可能的 a 排列，因此有 \sum \frac {\prod a_i}{\prod s_i}=1，分子为定值，因此答案为 \sum \frac {1}{\prod a_i}，容易 O(n^2) 背包。
k=2
那么直接 dp，记 $f_{i,j,k}$ 为考虑前 $i$ 个元素，$S$ 总和为 $j$，总共选了 $k$ 个元素的权值和。发现 $a_1$ 无需枚举，在转移时加入即可，只需多开一维记录 $a_1$ 是否确定。对于分子，转移时直接乘上；对于分母，不妨将 $a_1$ 记入 $j$ 最后除掉。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5, M = 1e4 + 5;
int n, m, op, mod, inv[M << 1];
int F[N][N], f[M][N][2], g[M][N][2];
inline int qstp(int a, int k) {int res = 1; for(; k; a = 1ll * a * a % mod, k >>= 1) if(k & 1) res = 1ll * res * a % mod; return res;}
inline void ADD(int &a, int b) {a += b; a = (a >= mod ? (a - mod) : a);}
signed main(){
// freopen("sum.in", "r", stdin);
// freopen("sum.out", "w", stdout);
cin >> n >> m >> op >> mod;
inv[0] = 1;
for(int i = 1; i < M << 1; ++i) inv[i] = qstp(i, mod - 2);
if(op == 1){
F[0][0] = 1;
for(int i = 1; i <= m; ++i){
F[i][0] = 1;
for(int j = 1; j <= n; ++j) F[i][j] = 1ll * (F[i - 1][j] + 1ll * F[i - 1][j - 1] * inv[i] % mod) % mod;
}
cout << F[m][n];
}
else{
f[0][0][0] = 1;
for(int i = 1; i <= m; ++i){
for(int j = 0; j <= i * (i - 1) / 2; ++j)
for(int k = 0; k <= min(i - 1, n); ++k) g[j][k][0] = f[j][k][0], g[j][k][1] = f[j][k][1];
for(int j = 0; j <= i * (i - 1) / 2; ++j){
for(int k = 0; k <= min(i - 1, n); ++k){
ADD(f[j + i][k + 1][0], 1ll * (mod - g[j][k][0]) * inv[i] % mod);
ADD(f[j][k + 1][0], 1ll * g[j][k][0] * inv[i] % mod);
ADD(f[j + i][k + 1][1], 1ll * (mod - g[j][k][1]) * inv[i] % mod);
ADD(f[j][k + 1][1], 1ll * g[j][k][1] * inv[i] % mod);
ADD(f[j + i][k + 1][1], 1ll * g[j][k][0] * i % mod);
}
}
}
int ans = 0;
for(int i = 0; i <= m * (m + 1) / 2; ++i) ADD(ans, 1ll * f[i][n][1] * inv[i] % mod);
cout << ans;
}
return 0;
}
```