当前位置: 首页 > news >正文

题解: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;
}
http://www.hskmm.com/?act=detail&tid=20085

相关文章:

  • 详细介绍:Linux----gcc、g++的使用以及一些问题
  • 同步和互斥的基本概念
  • Sep 28
  • 图像采集卡:连接镜头与机器的“视觉神经”,释放工业智能核心动力
  • 2025 年生态木厂商最新推荐榜单:TOP 前五企业实力解析及厂商选择指南生态木方通/户外地板/装饰线条/隔断/背景墙厂商推荐
  • 盲盒一番赏小应用用户需求分析:从行为动机到功能诉求的深度拆解
  • 解题报告-泥路(muddyroad.*)
  • 洛谷P10112 [GESP202312 八级] 奖品分配
  • P10400 『STA - R5』消失的计算机
  • 2025 地坪研磨机厂家推荐权威推荐排行榜:品牌深度解析及格力 / 宁德时代合作案例速递水磨石/遥控式/座驾式/小型地坪研磨机厂家推荐
  • 2025 年最新推荐铝塑膜源头厂家权威排行榜:聚焦 3000㎡厂房与完整产业链的优质企业盘点复合/防锈防潮/木箱包装/设备包装铝塑膜厂家推荐
  • 2025 年真空袋生产厂家最新权威推荐排行榜:TOP 级企业工艺、服务及适配场景全景对比指南木箱/设备/海运防潮/铝塑/电柜真空袋厂家推荐
  • 《码界飞升传II:数据星辰异界问道》
  • Win FAQ
  • 结论(数学)
  • loki收集容器日志
  • Xcode 火焰图
  • 完整教程:dlib库关键点定位和疲劳检测
  • 2025 长沙美食餐厅权威推荐排行榜:老店红记领衔新晋品牌,200 + 湘味与网红菜品深度解析,吃货必藏指南长沙美食湘菜馆 /大排档/网红店餐厅推荐
  • VKD233HH触控IC有两种输出方式“直接输出”和“锁存输出”单路触摸检测芯片
  • 打包present, but unavailable
  • 2025 年最新推荐环保门禁厂家权威排行榜:清洁运输 / 智能 / 移动源系统及电子台账厂商详析企业/智能环保门禁厂家推荐
  • 2025 年即时通讯公司推荐 小天互连:私有化部署即时通讯、信创即时通讯、国产化即时通讯、局域内网即时通讯、企业 IM 即时通讯解决方案解析
  • GJOI 模拟赛6、7部分题解
  • 【C++list】底层结构、迭代器核心原理与常用接口完成全解析
  • 完整教程:Flink Watermark机制解析
  • 2025 年北京湖南菜餐厅推荐:小湖南岸以湖湘本味与匠心服务,成京城湘菜口碑之选
  • Vector
  • SSM
  • Mybatis Plus