M-SOLUTIONS Programming Contest 题解
AB 就不写了。
C - Best-of-(2n-1)
题意
A 和 B 玩游戏，每一轮有 \(a\) 的概率 A 获胜，\(b\) 的概率 \(B\) 获胜，\(1-a-b\) 的概率平局。他们会一直玩直到某个人获胜了 \(n\) 轮。
求期望轮数。
\(n\le 10^5\)
题解
假设最后 A 获胜了 \(n\) 轮。考虑枚举 B 获胜的轮数 \(i\)，确定 A 和 B 获胜的轮的相对顺序后，那么还有 \(i+n\) 个空可以插入一段平局。一段平局加一轮不平局的期望轮数为 \[ \sum_{i=0}^{\infty}\left(1-a-b\right)^i=\frac{1}{a+b} \]
所以答案为 \[ \sum_{i=0}^{n}\binom{n-1+i}{i}\left(\frac{a}{a+b}\right)^n\left(\frac{b}{a+b}\right)^i(i+n)\frac{1}{a+b} \]
D - Maximum Sum of Minimum
题意
给定一棵 \(n\) 个点的树，将 \(c_1,c_2,\ldots,c_n\) 中的每个数填入树上的恰好一个点。定义一条边的边权为这条边连接的两个点上数字的较小值。
求所有边权之和的最大值，并构造一种填数方案。
\(n\le 10^4\)
题解
考虑从小到大填数。为了使大的数字贡献更多，我们一定会使当前数字的贡献尽量小。
那么我们从小到大填数，每次将当前数填入一个叶子，将该叶子删去即可。
时间复杂度 \(O(n\log n)\)。
E - Product of Arithmetic Progression
题意
\(Q\) 次询问，每次询问给定 \(x,d,n\)，求 \[ \prod_{i=0}^{n-1} (x+id) \]
对 \(P=10^6+3\) 取模。
\(Q\le 10^5,0\le x,d < P,n\le 10^9\)
题解
先考虑 \(d=1\) 的情况。若 \(x+d-1\ge P\) 或 \(x=0\)，那答案一定是 \(0\)，否则答案就是 \(\frac{(x+d-1)!}{(x-1)!}\)，直接预处理阶乘和阶乘逆元即可。
\(d>1\) 时，我们可以将式子化为 \[ d^n\prod_{i=0}^{n-1}\left(\frac{x}{d}+i\right) \]
就与 \(d=1\) 的情况一样了。注意特判 \(d=0\) 的情况。
F - Random Tournament
题意
有 \(N\) 个人参加比赛，给定两两之间比赛的输赢关系。
比赛规则是，先将 \(N\) 个人按 \(1\) 到 \(N\) 的顺序从左到右排列，每次随机相邻两个人进行比赛，输的人离开，直到剩下一个人，这个人就是冠军。
求有多少个人可能成为冠军。
\(N\le 2000\)
题解
一个朴素的区间 DP 是，令 \(f_{l,r,x}\) 表示只考虑 \([l,r]\) 中的人，\(x\) 是否可能成为冠军。转移则需要考虑 \([l,x-1]\) 中的冠军和 \([x+1,r]\) 中的冠军。
注意到对于所有 \(l < x < r\)，\(x\) 能在 \([l,r]\) 中取得冠军的充要条件是他在 \([l,x]\) 中能取得冠军，\([x,r]\) 中也能取得冠军。即有 \(f_{l,r,x}=f_{l,x,x}\land f_{x,r,x}\)。
于是我们只需要记录 \(x\in \{l,r\}\) 的状态即可，转移枚举 \([l+1,r]\) 或 \([l,r-1]\) 中的冠军即可。
写出转移式子后发现可以 bitset 优化。
时间复杂度 \(O(\frac{N^3}{w})\)。
