小红的点赞题解

显然，这道题具体的数是多少并不重要

我们只关心奇数与偶数的个数

设 $E_i$ 为奇数个数为 $i$ 时的还原为偶数的期望我们有

$E_i=E_{i-1}\frac{i}{n}+E_{i+1}\frac{n-i}{n}+1$

对于

$i=0$ 或 $i=n$ 有 $E_0=0$ 与 $E_n=E_{n-1}+1$

此处不依赖数学直觉，将其转换为 $d_i$ 使得 $d_i=E_i-E_{-1}$ 而是选择高斯消元

对于每一个 $E_i$ 表达式有 $-E_{i-1}\times\frac{i}{n}+E_i-E_{i+1}\times\frac{n-i}{n}=1$ 可列出行列式

1	0	0	...	...	...	...	0
$-\frac{1}{n}$	1	$-\frac{n-1}{n}$	...	...	...	...	1
0	$-\frac{2}{n}$	1	$-\frac{n-2}{n}$	...	...	...	1
...	...	...	...	...	...	...	1
...	...	...	...	$-\frac{n-1}{n}$	1	$-\frac{1}{n}$	1
...	...	...	...	...	-1	1	1

显然，只需要解出该行列式对应的方程组就可求出对应的 $E_i$

但高斯消元的时间复杂度为 $O(n^3)$ 不可能通过 $n=10^5$ 的数据

注意到该行列式十分特殊，每行最多只有三个值

此处使用TDMA(Thomas Algorithm)托马斯算法进行计算

本质其实是高斯消元剪枝，先只使用上一行的进行消元，变成上三角矩阵

再只使用下一行数据获取答案，具体做法请自行搜索

def thomas_algorithm(n, a, b, c, d):
    """
    求解方程组: 
    b[0] * x[0] + c[0] * x[1] = d[0]
    a[i] * x[i-1] + b[i] * x[i] + c[i] * x[i+1] = d[i], for i=1 to n-2
    a[n-1] * x[n-2] + b[n-1] * x[n-1] = d[n-1]
    """
    # 前向消元
    for i in range(1, n):
        w = a[i] / b[i-1]
        b[i] = b[i] - w * c[i-1]
        d[i] = d[i] - w * d[i-1]
    
    # 回代
    x = [0] * n
    x[n-1] = d[n-1] / b[n-1]
    for i in range(n-2, -1, -1):
        x[i] = (d[i] - c[i] * x[i+1]) / b[i]
    
    return x

如此便解决该题，附通过代码

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int pow(int a, int b, const int &m)
{
    long long res = 1, po = a;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * po % m;
        po = po * po % m;
    }
    return res;
}

// Returns the modular inverse of a prime modulo p.
int64_t inverse(int a, int p = mod)
{
    return pow(a, p - 2, p);
}
int main()
{
    int n;
    cin >> n;
    int64_t sum = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        sum += x;
        cnt += x & 1;
    }
    vector<int64_t> c(n + 1, 1);
    c[0] = 0;
    vector<array<int64_t, 3>> a(n + 1);
    a[0] = {0, 1, 0};
    int64_t inv_n = inverse(n);
    for (int i = 1; i < n; i++)
    {
        a[i][0] = (mod - i) * inv_n % mod;
        a[i][1] = 1;
        a[i][2] = (mod - (n - i)) * inv_n % mod;
    }
    a[n][0] = mod - 1;
    a[n][1] = 1;
    a[n][2] = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = a[i][0] * inverse(a[i - 1][1]) % mod;
        for (int j = 1; j < 3; j++)
        {
            a[i][j - 1] -= t * a[i - 1][j] % mod;
            a[i][j - 1] = (a[i][j - 1] + mod) % mod;
        }
        c[i] -= (c[i - 1] * t) % mod;
        c[i] = (c[i] + mod) % mod;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        int t = a[i][2] * inverse(a[i + 1][1]) % mod;
        for (int j = 1; j <= 2; j++)
        {
            a[i][j] -= t * a[i + 1][j - 1] % mod;
            a[i][j] = (a[i][j] + mod) % mod;
        }
        c[i] -= (c[i + 1] * t) % mod;
        c[i] = (c[i] + mod) % mod;
    }
    cout << (sum + c[cnt] * inverse(a[cnt][1]) % mod) % mod;
    return 0;
}

题解 | #小红的点赞#

小红的点赞题解