小红的点赞

[题目链接](https://www.nowcoder.com/practice/14a793274f5a489982bce57043e65292)

思路

有 $n$ 篇笔记，初始点赞数为 $a_1, a_2, \ldots, a_n$ 。每个时间步，随机等概率选一篇笔记使其点赞 $+1$ 。求第一次所有笔记点赞数均为偶数时，总赞数之和的期望，答案对 $10^9+7$ 取模。

关键观察：只有奇偶性重要

每一步只改变一篇笔记的奇偶性，因此我们只需关注"有多少篇笔记的点赞数为奇数"。设当前有 $k$ 篇笔记点赞数为奇数，则：

以概率 $\frac{k}{n}$ ，选中一篇奇数笔记，它变为偶数，状态变为 $k-1$ ；
以概率 $\frac{n-k}{n}$ ，选中一篇偶数笔记，它变为奇数，状态变为 $k+1$ 。

这是一个经典的生灭链（Birth-Death Chain），状态空间为 $\{0, 1, \ldots, n\}$ ，目标是从初始状态 $k$ 到达吸收态 $0$ 。

期望步数转化为期望总赞数

注意每走一步，总赞数恰好 $+1$ 。因此：

$ $E[\text{总赞数}] = \text{初始总赞数} + E[\text{步数}]$ $

问题转化为求从状态 $k$ 到状态 $0$ 的期望步数 $f_k$ 。

生灭链期望到达时间公式

对于从状态 $i$ 出发的生灭链，令出生率 $\lambda_i = \frac{n-i}{n}$ ，死亡率 $\mu_i = \frac{i}{n}$ 。

定义测度 $\pi_i = \prod_{j=1}^{i} \frac{\lambda_{j-1}}{\mu_j} = \prod_{j=1}^{i} \frac{n-j+1}{j} = \binom{n}{i}$ 。

由生灭链理论，从状态 $k$ 到状态 $0$ 的期望步数为：

$ $f_k = \sum_{i=1}^{k} \frac{1}{\mu_i \cdot \pi_i} \sum_{j=i}^{n} \pi_j = \sum_{i=1}^{k} \frac{n}{i \cdot \binom{n}{i}} \cdot S_i$ $

其中 $S_i = \sum_{j=i}^{n} \binom{n}{j} = 2^n - \sum_{j=0}^{i-1} \binom{n}{j}$ 。

计算过程

预处理阶乘及其逆元，用于快速计算 $\binom{n}{i}$ ；
从 $i=1$ 到 $k$ 递推前缀和 $\sum_{j=0}^{i-1}\binom{n}{j}$ ，从而得到 $S_i$ ；
累加每一项 $\frac{n}{i \cdot \binom{n}{i}} \cdot S_i$ ，得到 $f_k$ ；
最终答案为 $(\text{初始总和} + f_k) \bmod (10^9+7)$ 。

样例演示

输入 $n=2$ ， $a=[1,2]$ ：初始总和 $=3$ ，奇数笔记数 $k=1$ 。

$f_1 = \frac{2}{1 \cdot \binom{2}{1}} \cdot S_1 = \frac{2}{2} \cdot (2^2 - \binom{2}{0}) = 1 \times 3 = 3$

答案 $= 3 + 3 = 6$ ，与样例一致。

复杂度分析

时间复杂度： $O(n)$ ，预处理阶乘和逆元后，求和过程为线性。
空间复杂度： $O(n)$ ，存储阶乘数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long power(long long a, long long b, long long mod) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long inv(long long a) {
    return power(a, MOD - 2, MOD);
}

int main() {
    int n;
    scanf("%d", &n);

    long long sum = 0;
    int k = 0;
    for (int i = 0; i < n; i++) {
        long long a;
        scanf("%lld", &a);
        sum = (sum + a) % MOD;
        if (a % 2 == 1) k++;
    }

    if (k == 0) {
        printf("%lld\n", sum);
        return 0;
    }

    vector<long long> fact(n + 1), ifact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = inv(fact[n]);
    for (int i = n - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1) % MOD;

    auto C = [&](int a, int b) -> long long {
        if (b < 0 || b > a) return 0;
        return fact[a] % MOD * ifact[b] % MOD * ifact[a - b] % MOD;
    };

    long long pow2n = power(2, n, MOD);
    long long prefix = 0;
    long long fk = 0;

    for (int i = 1; i <= k; i++) {
        prefix = (prefix + C(n, i - 1)) % MOD;
        long long Si = (pow2n - prefix + MOD) % MOD;
        long long cni = C(n, i);
        long long term = (long long)n % MOD * inv(i) % MOD * inv(cni) % MOD * Si % MOD;
        fk = (fk + term) % MOD;
    }

    printf("%lld\n", (sum + fk) % MOD);
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007;

    static long power(long a, long b, long mod) {
        a %= mod;
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    static long inv(long a) {
        return power(a, MOD - 2, MOD);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            sum = (sum + a) % MOD;
            if (a % 2 == 1) k++;
        }

        if (k == 0) {
            System.out.println(sum);
            return;
        }

        long[] fact = new long[n + 1];
        long[] ifact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
        ifact[n] = inv(fact[n]);
        for (int i = n - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1) % MOD;

        long pow2n = power(2, n, MOD);
        long prefix = 0;
        long fk = 0;

        for (int i = 1; i <= k; i++) {
            long cni1 = fact[n] % MOD * ifact[i - 1] % MOD * ifact[n - i + 1] % MOD;
            prefix = (prefix + cni1) % MOD;
            long Si = (pow2n - prefix + MOD) % MOD;

            long cni = fact[n] % MOD * ifact[i] % MOD * ifact[n - i] % MOD;
            long term = (long) n % MOD * inv(i) % MOD * inv(cni) % MOD * Si % MOD;
            fk = (fk + term) % MOD;
        }

        System.out.println((sum + fk) % MOD);
    }
}