闲话
symbolic method 写了 7k 了（
感觉能写很多的样子！
有人膜我 说我多项式全家桶就剩三道了
我当机立断说 这话显然 fake 我还特地核查了
然后那人想挂我来着 我就和他说：我特地核查了 你这话就是错的
他倒是来劲了
我倒要看看是谁挂谁
？
杂题
今天模拟赛 T3 的弱化版是 Round #641 的题，部分分是那题
然后题解就写了啊：《之前 CF div1 D 原题，算是给⼤家送分了。》
？那我要是搬来这场的 F2 原题 是不是也给大家送了 100 分？
我希望我能搬来 CF1349F2 然后放在 T1 的位置呢！给大家送 100 分！
哦我懂了 题解的意思是除了我以外所有人都可以场切 CF1349D 的意思吧
那就是我的功夫不到家了
各位太强了 爆踩 tourist
有 \(n\) 个人, 第 \(i\) 个人有 \(a_i\) 个饼干。每次随机选择一个饼干, 将其随机分配给除了它现在所有者的其他 \(n-1\) 个人。求使得一个人拥有所有饼干的期望步数, 对 \(998244353\) 取模。
\(n\le 5\times 10^6, \sum a_i \le 10^7\)。
设 \(P[X_i]\) 为最后饼干全在第 \(i\) 个人处的概率，\(E[X_i]\) 为这一部分概率下的期望步数。
答案即为 \(\sum_{i= 1}^n E[X_i]\)。也可以发现 \(\sum P[X_i] = 1\)。
设 \(E_0[X_i]\) 为只有当饼干全在第 \(i\) 个人处时游戏才能结束的情况下，饼干全在第 \(i\) 个人处的期望步数。
我们发现，\(E_0[X_i]\) 是好求的，因此我们寻找用 \(E_0[X_i]\) 表示 \(E[X_i]\) 的方案。这时就必须考虑到另一个人 \(j\) 拿到所有饼干的情况，并从这种情况转移。可以发现 \(\forall i, j\)，把所有饼干从 \(i\) 处转移到 \(j\) 的期望步数是相同的，记作 \(C\)。
我们可以确定 \(i\)，枚举 \(j\)，写出
\[E[X_i] = E_0[X_i] - \sum_{j \neq i} \left( P[X_j]\times C + E[X_j] \right) \]也就是
\[\sum_{j = 1}^n E[X_j] = E_0[X_i] - \sum_{j \neq i} P[X_j]\times C \]我们记 \(\text{ans} = \sum_{i= 1}^n E[X_i]\)，并两边对 \(i\) 求和得到
\[n\times \text{ans} = \sum_{i = 1}^n E_0[X_i] - C(n - 1) \sum_{j = 1}^n P[X_j] = \sum_{i = 1}^n E_0[X_i] - C(n - 1) \]因此我们只需要求得每个 \(E_0[X_i]\) 和 \(C\)。
发现每个人本质上是等价的，因此我们可以只记录 \(f(k)\) 为某个人最开始手中有 \(k\) 块饼干的情况下取得所有饼干的期望。可以发现 \(E_0[X_i] = f(a_i), C = f(0)\)。
然后我们只需要讨论各种情况并转移即可。设 \(m = \sum a_i\)，不难得到
\[f(k) = \left\{ \begin{aligned} & \frac{1}{n - 1} f(k + 1) + \frac{n - 2}{n - 1} f(k) + 1 \ , && k = 0 \\ & \frac{m - k}{m} \left( \frac{1}{n - 1} f(k + 1) + \frac{n - 2}{n - 1} f(k) \right) + \frac{k}{m} f(k - 1) \ , && 0 < k < m \\ & 0 \ , && k = m \end{aligned} \right. \]下面关注 \(0 < k < m\) 的情况对应的式子。可以发现左右两侧 \(f\) 的系数之和都为 \(1\)，因此如果将 \(f\) 做差分则这个式子能应用在差分上，求和号内与 \(k - 1, k, k + 1\) 无关的项都可以消去。
我们设 \(g(i) = f(i) - f(i + 1), g(m) = 0\)，则 \(f(k) = \sum_{i = k}^m g(i)\)。这样带入式子能得到
\[\sum_{i = k}^m g(i) = \frac{m - k}{m} \left( \frac{1}{n - 1} \sum_{i = k + 1}^m g(i) + \frac{n - 2}{n - 1} \sum_{i = k}^m g(i) \right) + \frac{k}{m} \sum_{i = k - 1}^m g(i) \]化简得到
\[g(k) = 1 + \frac{(m - i) (n - 2)}{m (n - 1)} g(k) + \frac{k}{m} (g(k) + g(k - 1)) \]移个项得到
\[g(i) = \frac{m(n - 1) + i(n - 1) g(i - 1)}{m - i} \]可以直接视 \(g(-1) = 0\)，\(g(0)\) 可以直接带入得到值为 \(n - 1\)。
直接计算即可，不难从 \(g\) 得到答案。
总时间复杂度 \(O(n + m)\)。
鞅和停时定理等 symbolic method 写完再说吧（
标签：right,饼干,闲话,31,步数,23.1,frac,times,sum From： https://www.cnblogs.com/joke3579/p/chitchat230131.html