REAL689 小红的点赞

题目链接

小红的点赞

题目描述

小红有 $n$ 篇笔记，初始点赞数分别为 $a_1, a_2, \dots, a_n$ 。在每个时间单位，都会有一篇随机的笔记（ $n$ 篇中的任意一篇，概率均等）点赞数加 1。

问：当第一次出现所有笔记的点赞数均为偶数时，所有笔记的总点赞数之和的期望是多少？

答案需要对 $1,000,000,007$ 取模。

解题思路

这是一个求解期望值的过程，通常可以通过动态规划（特别是期望 DP）来解决。

状态定义

我们关心的是所有笔记点赞数的奇偶性。因此，系统的关键状态可以被简化为当前点赞数为奇数的笔记数量。设这个数量为 $k$ 。我们的目标是从初始状态（有 $k_{initial}$ 个奇数赞的笔记）到达目标状态（ $k=0$ ）。
期望的递推关系

设 $E_k$ 为从当前有 $k$ 个奇数赞笔记的状态，到第一次变为有 0 个奇数赞笔记的状态，所需要增加的点赞数的期望值。

当我们处于状态 $k$ 时（ $0 < k \le n$ ），下一步会发生什么：
- 我们随机选择一篇笔记点赞。
- 有 $\frac{k}{n}$ 的概率，我们选中了一篇奇数赞的笔记。点赞后，它的赞数变为偶数。系统中奇数赞笔记的数量变为 $k-1$ 。
- 有 $\frac{n-k}{n}$ 的概率，我们选中了一篇偶数赞的笔记。点赞后，它的赞数变为奇数。系统中奇数赞笔记的数量变为 $k+1$ 。
根据期望的线性性质，我们可以建立 $E_k$ 的递推关系：

$[ E_k = 1 + \frac{k}{n} \cdot E_{k-1} + \frac{n-k}{n} \cdot E_{k+1} ]$

这里的 1 代表当前这一步增加的 1 个点赞。

我们的目标是求解 $E_{k_{initial}}$ ，其中 $k_{initial}$ 是初始时点赞数为奇数的笔记数量。
解递推方程

这是一个包含 $E_{k-1}, E_k, E_{k+1}$ 的三项递推式。直接求解比较困难。我们可以通过引入差分来简化它。

定义 $d_k = E_k - E_{k-1}$ 。

对原递推式进行变形，可以得到 $d_k$ 之间的关系：

$[ d_k = \frac{(n-k) \cdot d_{k+1} + n}{k} ]$

这个新的递推式允许我们从 $d_{k+1}$ 计算出 $d_k$ 。

我们需要一个边界条件。考虑 $k=n$ 的情况，此时所有笔记都是奇数赞。无论点赞哪一篇，都会使其变为偶数，状态必然转移到 $n-1$ 。所以：

[ $E_n = 1 + E_{n-1}$ ]

这意味着 $d_n = E_n - E_{n-1} = 1$ 。

有了这个边界条件，我们就可以从 $d_n=1$ 开始，反向递推出 $d_{n-1}, d_{n-2}, \dots, d_1$ 。
计算最终答案
- 首先，计算初始的总赞数 $S_{initial}$ 和奇数赞笔记的数量 $k_{initial}$ 。
- 如果 $k_{initial}=0$ ，说明初始状态就满足条件，期望增加的点赞数为 0，答案就是 $S_{initial}$ 。
- 否则，使用 $d_n=1$ 和递推式计算出 $d_n, \dots, d_1$ 。
- 我们要求的 $E_{k_{initial}}$ 可以通过差分求和得到：
  
  $[ E_{k_{initial}} = (E_{k_{initial}} - E_0) = \sum_{i=1}^{k_{initial}} (E_i - E_{i-1}) = \sum_{i=1}^{k_{initial}} d_i ]$
  
  （因为我们的目标状态是 $k=0$ ，所以 $E_0=0$ ）
- 最终的期望总赞数就是 $S_{initial} + E_{k_{initial}}$ 。
注意：在计算 $d_k$ 的过程中，涉及到除以 $k$ 的操作。在模运算下，除法需要用乘以其模逆元来代替。由于模数 $1,000,000,007$ 是一个质数，我们可以用费马小定理来计算模逆元。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000007;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000007;
        base = (base * base) % 1000000007;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 1000000007 - 2);
}

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long initial_sum = 0;
    int odd_count = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        initial_sum = (initial_sum + a[i]) % 1000000007;
        if (a[i] % 2 != 0) {
            odd_count++;
        }
    }

    if (odd_count == 0) {
        cout << initial_sum << endl;
        return;
    }

    vector<long long> d(n + 1);
    d[n] = 1;

    for (int i = n - 1; i >= 1; --i) {
        long long term1 = ((long long)(n - i) * d[i + 1]) % 1000000007;
        long long numerator = (term1 + n) % 1000000007;
        d[i] = (numerator * modInverse(i)) % 1000000007;
    }

    long long expected_steps = 0;
    for (int i = 1; i <= odd_count; ++i) {
        expected_steps = (expected_steps + d[i]) % 1000000007;
    }

    long long final_expectation = (initial_sum + expected_steps) % 1000000007;
    cout << final_expectation << endl;
}

int main() {
    solve();
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    public static long modInverse(long n) {
        return power(n, MOD - 2);
    }

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

        if (oddCount == 0) {
            System.out.println(initialSum);
            return;
        }

        long[] d = new long[n + 1];
        d[n] = 1;

        for (int i = n - 1; i >= 1; i--) {
            long term1 = ((long) (n - i) * d[i + 1]) % MOD;
            long numerator = (term1 + n) % MOD;
            d[i] = (numerator * modInverse(i)) % MOD;
        }

        long expectedSteps = 0;
        for (int i = 1; i <= oddCount; i++) {
            expectedSteps = (expectedSteps + d[i]) % MOD;
        }

        long finalExpectation = (initialSum + expectedSteps) % MOD;
        System.out.println(finalExpectation);
    }
}

MOD = 1000000007

def power(base, exp):
    res = 1
    base %= MOD
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % MOD
        base = (base * base) % MOD
        exp //= 2
    return res

def mod_inverse(n):
    return power(n, MOD - 2)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    initial_sum = sum(a) % MOD
    odd_count = sum(1 for x in a if x % 2 != 0)
    
    if odd_count == 0:
        print(initial_sum)
        return
        
    d = [0] * (n + 1)
    d[n] = 1
    
    for i in range(n - 1, 0, -1):
        term1 = ((n - i) * d[i + 1]) % MOD
        numerator = (term1 + n) % MOD
        d[i] = (numerator * mod_inverse(i)) % MOD
        
    expected_steps = sum(d[i] for i in range(1, odd_count + 1)) % MOD
    
    final_expectation = (initial_sum + expected_steps) % MOD
    print(final_expectation)

if __name__ == "__main__":
    solve()

算法及复杂度

算法：期望动态规划
时间复杂度： $O(N \log M)$ ，其中 $N$ 是笔记的数量， $M$ 是模数。
- 计算初始状态耗时 $O(N)$ 。
- 计算 $d$ 数组需要一个大小为 $N$ 的循环，循环内部的主要开销是计算模逆元，使用快速幂需要 $O(\log M)$ 的时间。
- 最后求和需要 $O(N)$ 。
- 因此总时间复杂度为 $O(N \log M)$ 。
空间复杂度： $O(N)$ 。
- 需要一个大小为 $N+1$ 的数组来存储差分值 $d_i$ 。

题解 | #小红的点赞#

REAL689 小红的点赞

题目链接

题目描述

解题思路

代码

算法及复杂度