description
给定正整数 \(n,m\) 和集合 \(S\)，满足 \(S\) 中元素互不相同且都是小于等于 \(m\) 的正整数。每次进行如下操作
-
从集合 \(S\) 中随机选取一个数记作 \(x\)
-
从 \(S\) 中删去 \(x\)
-
如果 \(x+1\leq m\) 且 \(x+1\) 不在 \(S\) 中，把 \(x+1\) 放入 \(S\)
求把集合清空的期望次数。
- \(n,m,|S|\leq 500\)
solution
数据范围诈骗。
可以发现，一个数对答案的贡献不受比它小的数的影响，只需要考虑每个数合并到第一个比它大的数的期望步数（或者最后一个数合并到 \(m+1\)），依据期望的线性性把每个数的期望步数加起来即为答案。
于是问题转化成这样独立的模型：
已知两数分别为 \(x,y(x\leq y)\)，
-
若 \(y\neq m+1\)，随机把 \(x\) 或 \(y\) 加 1。
-
若 \(y=m+1\)，把 \(x\) 加 1。
求 \(f_{x,y}\) 表示使得初始的 \(x,y\) 相等 x 的期望增加步数。
显然有转移：
-
\(f_{i,i}=0\)
-
\(f_{i,j}=\dfrac{(f_{i+1,j}+1)+f_{i,j+1}}{2}\)
-
\(f_{i,m+1}=f_{i+1,m+1}+1\)
时间复杂度 \(O(m^2)\)
code
代码里的状态 \(x,y\) 分别表示第一个数和第二个数到 \(m+1\) 的距离。
Submission #230364270 - Codeforces