123
K
场上想到了 \(f_{l,r,x,y}\) 表示左边 \(x\) 个右边 \(y\) 个，但是绝对值是可以直接拆开来的，所以只需要存一个 \(f_{l,r,c}\) 表示左边次数 \(-\) 右边次数为 \(c\) 即可，这个 \(c\) 显然是 \(O(\log n)\) 级别的，转移也很好写。
需要注意的是题目是给出 \(y\) 回答是否 \(x \geq y\)，不是相等就结束的，写代码的时候这里卡了一下。
M
只考虑 \(p\in (0.5,1)\)，其余情况平凡。
假设左侧盒子 \(x\) 次，右侧 \(y\) 次，则左侧的概率为 \(\frac{p^x(1-p)^y}{p^x(1-p)^y + (1-p)^xp^y}=\frac{p^{x-y}}{p^{x-y}+(1-p)^{x-y}}\)，只与 \(x-y\) 有关。
于是枚举 \(|x-y|=n\)，考虑 \(f(i)\) 表示 \(x-y=i\) 时距离 \(x-y=n\) 还需要的期望步数，有 \(f(i)=p\cdot f(i+1)+(1-p)\cdot f(i-1)+1\)，是线性高斯消元形式，考虑 \(g(i)=g(i+1)-g(i)\)，有 \(g(i)=\frac{(1-p)g(i-1)-1}{p}\)，利用 \(f(-n)=f(n)=0,f(n)=f(-n)+\sum g(i)=0\) 求解整理得 \(f(0)=\frac{n((1-p)^n-p^n)}{(1-2p)((1-p)^n+p^n)}\)。
之后暴力枚举一下即可。
实现的话 Python 有方便的分数类fractions以及高精度，很香。
1 | from fractions import Fraction as frac |
C
每一步我都会，合起来就寄，爆笑
条件概率先考虑对答案贝叶斯，假设做对\(k\)题的选法中，选项均分的概率是\(g_k\)，假设做对\(k\)题的所有选法中，选项均分的选法是\(f_k\)，那么\(g_k=\frac{f_k}{\binom nk (m-1)^{n-k}}\)。答案就是\(\frac{\sum_{i=0}^n p_ig_ii}{\sum_{i=0}^n p_i g_i}\)。
然后考虑\(f_k\)怎么算。我们可以考虑先算\(h_k\)表示选项均分，且指定了某\(k\)个做对，剩下随意的方案数之和，那么\(h_k=\sum_{i=0}^k\binom ki f_i\)，反演能从\(h\)得到\(f\)。然后考虑求\(h\)。我们不妨假设答案是\(aa...abb...bcc...c.......\)，这样方便考虑。然后设\(dp_{i,j}\)表示已经填好了前\(i\)种答案对应的所有题，其中钦定正确的有\(j\)个，剩下的可以打乱顺序填。我们可以枚举第\(i\)个选项对应的题目种有多少个填对了，假设\(c_i\)个，那么\(dp_{i,j}\)可以从\(dp_{i-1,j-c_i}\)转移。最后填完了这些正确的答案之后，那些错误的答案还要随便乱序填，但是能拿来填的每种选项个数是已经定好的，第\(i\)个选项对应的题里面有\(c_i\)个填对了，就必须还要再填\(\frac nm-c_i\)个\(i\)选项。因此最后\(dp\)出来的每个\(dp_{m,k}\)都还要再乘上一个\(\binom{n-k}{\frac nm-c_1,\frac nm-c_2,...,\frac nm-c_m}\)，那我们把下面的阶乘倒数在\(dp\)转移的时候乘进去，所以转移是\(dp_{i,j}+=\frac{dp_{i-1,j-c_i}\binom{\frac nm}{c_i}}{(\frac nm-c_i)!}\)。然后\(h_k=dp_{m,k}(n-k)!\)，\(f_k=\sum_{i=0}^k(-1)^{k-i}\binom ki h_i\)。
然后\(dp\)的状态数\(O(nm)\)，枚举\(c_i\)转移是\(O(\frac nm)\)，最终复杂度是\(O(n^2)\)。