先把所有数都减一，n 表示进行了 n 个回合。

设 E[i] 为最后 i 出现的期望次数。那么显然 E[n] 最容易求，就是每次都 p，E[0] 也容易求，每个回合的 delta 只与当前有多少个 0 有关，看起来可以递推。
E[n-1] 则需要讨论一下，E[n-2] 就更要讨论了。

仔细观察，我们发现不得不枚举第一次出现 i 的时刻，设 A[i][j] 等于 i 第一次出现在 j 时刻的概率，我们有：

E[i] = A[i][j] B[n-j] | j = 0..n

这里 B[i] 表示当前最高位后续再进行 i 个回合期望出现多少次，和求 E[0] 类似，这个值只与后续进行的回合数有关！

进一步，考察 A[i][j]，最后第 j 时刻必然是 p 事件，前面二项分布即可：

A[i][j] = C(j-1, i-1) p^i (1-p)^(j-i)

考察 B[i] 有：

B[0] = 1
B[i] = B[i-1] + B[i-1] / n-i

于是可以得到暴力 O(n2) dp。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;

const int N = 1009;
Int Fact[N], iFact[N];
Int E[N], A[N], B[N];
int n, p, q;

Int Binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return Fact[n] * iFact[m] * iFact[n-m];
}

int main(){
    MOD = 998244353; RD(n, p); p = Int(p) / 100; q = Int(1) - p;
    Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;
    iFact[n] = _I(Fact[n]); DWN_1(i, n, 1) iFact[i-1] = iFact[i] * i;
    B[0] = 1; FOR(i, 1, n) B[i] = B[i-1] * (q+n-i) / (n-i);

<pre><code>E[0] = B[n-1]; FOR(i, 1, n) {
    FOR(j, i, n) E[i] += Binom(j-1, i-1) * pow(p, i) * pow(q, j-i) * B[n-1-j];
}

REP(i, n) printf(&amp;quot;%d\n&amp;quot;, E[i]);
</code></pre>

}

再卷积即可。

Posted by xiaodao
Category: 日常