题解 | #解封#

将期望表达式按定义写出后提取公因子，具体步骤：

为了书写方便，令$p_i=1\mathrm{/}{p}_{i}p\_i\; =\; 1\; /\; p\_i$，$q_i={\prod }_{j=1}^i(1-p_j)q\_i\; =\; \backslash prod\_\{j=1\}^i\{(1\; -\; p\_j)\}$，特别的令$q_0=1q\_0\; =\; 1$，

$E_x=p_1\times 1+q_1{p}_2\times 2+\mathrm{.}\mathrm{.}\mathrm{.}+q_{n-1}{p}_n\times nE\_x\; =\; p\_1\; \backslash times\; 1\; +\; q\_1\; p\_2\; \backslash times\; 2\; +\; ...\; +\; q\_\{n\; -\; 1\}\; p\_n\; \backslash times\; n$

​ $+q_n{p}_1\times (n+1)+q_n{q}_1{p}_2\times (n+2)+\mathrm{.}\mathrm{.}\mathrm{.}+q_n{q}_{n-1}{p}_n\times (n+n)+\; q\_n~p\_1\; \backslash times\; (n\; +\; 1)\; +\; q\_n~q\_1\; p\_2\; \backslash times\; (n\; +\; 2)\; +\; ...\; +\; q\_n~q\_\{n\; -\; 1\}\; p\_n\; \backslash times\; (n\; +\; n)$

​ $+{q_n}^2{p}_1\times (2n+1)+{q_n}^2{q}_1{p}_2\times (2n+2)+\mathrm{.}\mathrm{.}\mathrm{.}+{q_n}^2{q}_{n-1}{p}_n\times (2n+n)+\; \{q\_n\}^2~p\_1\; \backslash times\; (2n\; +\; 1)\; +\; \{q\_n\}^2~q\_1\; p\_2\; \backslash times\; (2n\; +\; 2)\; +\; ...\; +\; \{q\_n\}^2~q\_\{n\; -\; 1\}\; p\_n\; \backslash times\; (2n\; +\; n)$

​ $+\mathrm{.}\mathrm{.}\mathrm{.}+...$

单独对$i\in [1,n]i\backslash in[1,n]$的列求和

$E_x={\sum }_{i=1}^n{\sum }_{j=0}^{+\mathrm{\infty }}({q_n}^j{q}_{i-1}{p}_i\times (jn+i))E\_x\; =\; \backslash sum\_\{i=1\}^n\; \backslash sum\_\{j=0\}^\{+\backslash infty\}\; (\{q\_n\}^j~q\_\{i\; -\; 1\}~p\_i\; \backslash times\; (jn\; +\; i))$

$={\sum }_{i=1}^n(q_{i-1}{p}_i{\sum }_{j=0}^{+\mathrm{\infty }}({q_n}^j\times (jn+i)))=\; \backslash sum\_\{i=1\}^n\; (q\_\{i\; -\; 1\}~p\_i\; \backslash sum\_\{j=0\}^\{+\backslash infty\}\; (\{q\_n\}^j\; \backslash times\; (jn\; +\; i)))$

现在只需求出${\sum }_{j=0}^{+\mathrm{\infty }}({q_n}^j\times (jn+i))\backslash sum\_\{j=0\}^\{+\backslash infty\}\; (\{q\_n\}^j\; \backslash times\; (jn\; +\; i))$

很明显这是一个等比数列$\times \backslash times$等差数列，用高中学的错位相减即可求和，求和后再求下极限就可以得出结果式子了。

(这个求和应该不用写了吧，用markdown不怎么好写，要把所有项列出来，不会的可以求助下高中数学老师)

最终对于$i\in [1,n]i\backslash in[1,n]$的所有项都可以先预处理后在$O(1)O(1)$复杂度内得到结果，总时间复杂度$O(n)O(n)$

const int N = 1e5 + 10, M = 1e6 + 10;

int p[N];

int quickpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * x % mod1;
        k >>= 1;
        x = x * x % mod1;
    }
    return res;
}

int inv(int x)
{
    return quickpow(x, mod1 - 2);
}

void solve(int Case)
{
    int n = read();
    for(int i = 1;i <= n;i ++) p[i] = read();
    for(int i = 1;i <= n;i ++)
        p[i] = p[i] * inv(100) % mod1;
    int q = 1;
    for(int i = 1;i <= n;i ++)
        q = q * ((1 + mod1 - p[i]) % mod1) % mod1;

    int res = 0;
    int temp = n * q % mod1 * inv((1 + mod1 - q) % mod1) % mod1 * inv((1 + mod1 - q) % mod1) % mod1;
    for(int i = 1, last = 1;i <= n;i ++)
    {
        res = (res + (i * inv((1 + mod1 - q) % mod1) % mod1 + temp) % mod1 * p[i] % mod1 * last % mod1) % mod1;
        last = last * ((1 + mod1 - p[i]) % mod1) % mod1;
    }

    printf("%lld\n", res);
}

signed main()
{
//    ios;
    int t = 1;// t = read();
    for(int i = 1;i <= t;i ++) solve(i);
    return 0;
}