题解：P10792 『SpOI - R1』笑起来最帅的小孩

· · 题解

Description

给定序列 a 及 初始为空的序列 b，将 a 中的数依次随机插入到 b 的任意一个位置，求最终的 b 转化为十进制数后的期望值。

Analysis

设 a 的元素总和 s = \sum\limits_{i=1}^k x_i\cdot l_i，a 的长度 n=\sum\limits_{i=1}^k l_i。

由于插入位置随机，a 中的任意一个元素出现在 b 的任意一个位置的概率相等，均为 \frac{1}{n}。对于最终十进制数第 j(j\in[0,n)) 位，该位置的期望数值为 \frac{s}{n}，对总期望的贡献为 \frac{s}{n}\cdot10^j。根据期望的线性性，总期望即为 \sum\limits_{j=0}^{n-1}\left( \frac{s}{n}\cdot10^j\right)=\frac{s}{n}\cdot\sum\limits_{j=0}^{n-1}10^j=\frac{s}{n}\cdot\frac{10^n-1}{9}。

总时间复杂度 \mathcal O(T\cdot(k+\log p))。

Code

#include"bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e5 + 5, mod = 2007072007;
int t, k;
int fpow(int a, int b) {
    int re = 1;
    while (b) {
        if (b & 1) 
            re = (__int128)re * a % mod;
        a = (__int128)a * a % mod;
        b >>= 1;
    }
    return re;
}
signed main() {
    cin >> t;
    while (t--) {
        cin >> k;
        int s = 0, n = 0;
        for (int i = 1, x, l; i <= k; i++) {
            cin >> x >> l;
            s += x * l;
            n += l;
        }
        __int128 ans = s;
        ans = ans * (fpow(10, n) - 1) % mod;
        ans = (ans % mod + mod) % mod;
        ans = ans * fpow(n, mod - 2) % mod * fpow(9, mod - 2) % mod;
        cout << (int)ans << '\n';
    }
    return 0;
}