MOD = 1000000007

# 扩展欧几里得算法
def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)


def mod_inverse(p, q):
    g, x, _ = extended_gcd(p, q)
    if g != 1:
        raise ValueError(f"{p} 和 {q} 不互质，无法找到模逆元")
    else:
        # 确保结果是正数
        inverse = x % q
        return inverse


n = int(input())
s = 0
m = 0
T = input().split()
for t in T:
    tmp = int(t)
    bt = tmp % 2
    s += tmp
    m += bt

a = [[0, 0] for _ in range(n)]
a[n - 1] = [1, 1]

for i in range(n - 1, 0, -1):
    a[i - 1][1] = a[i][1] * i
    a[i - 1][0] = (a[i][0] + a[i][1]) * (n - i) + a[i - 1][1]
    a[i - 1][0] %= MOD
    a[i - 1][1] %= MOD
    g, _, _ = extended_gcd(a[i - 1][0], a[i - 1][1])
    a[i - 1][0] //= g
    a[i - 1][1] //= g

b = [0] * (n + 1)
for i in range(m):
    b[i] = a[i][0] * mod_inverse(a[i][1], MOD) % MOD
    s += b[i]

s %= MOD
print(s)

问题拆解

每次操作，总点赞数+1，因此，最终点赞数=最初点赞数+随机事件发生总次数

可以明显看到，各个笔记点赞数之间地位无差别，且具体值并不重要，重要的只有点赞数之和以及当前状态（剩余多少个奇数）。

因此，问题的核心就很明显了：一共 n 个数，其中有 m 个奇数，每一步会随机地有一个数改变自己的奇偶性，求解当所有数都成为偶数时的期望步数（求出步数再加上初始点赞和s0）

显然，这是一个动态规划问题。

动态规划

让我们将剩余i个奇数的状态记作状态 i ，状态 i 走到 i - 1 的步数X(i-1)的期望记作 x(i-1) = q(i-1)/p(i-1) 。

由于目标是全部偶数，也就是状态0，这里将奇数减少称为前进，增多称为后退。

在动态规划问题中，推算某个变量X的期望x时，引用了另一期望为y变量Y，可以将Y当成固定为y的常量以简化推理。

从 n（全奇数）到 n - 1：

步数 X(n-1) = 1 （q(n-1)=p(n-1)=1）

从 i 到 i - 1：

(0) 后退0次，概率 i/n ，1步

(1) 后退1次，概率 ((n-i)/n)*(i/n)，1+1+Xi 步

……

(k) 后退k次，概率 ((n-i)/n)^k*(i/n)，1+(1+Xi)*k 步

……

求和，得到

x(i-1) = i/n * 1 + ((n-i)/n)*(i/n) * (1+1+Xi) + …… + ((n-i)/n)^k*(i/n) * (1+(1+Xi)*k) + ……

用Xi的期望xi替换Xi，计算得到：

x(i-1) = 1 + (1+xi) * ((n-i)/i)

也就是

p(i-1)_tmp = pi * i

q(i-1)_tmp = (qi + pi) * (n-i) + p(i-1)_tmp

p(i-1)_tmp q(i-1)_tmp约分后得到p(i-1)、q(i-1)

从 m 到 0

依据以上递推关系和初值，一直从x(n-1)推算到x0，将它们存放到一个数组中。

题目所要求的从m到0，即计算 total = x0+x1+…+x(m-1) mod 1000000007

实际操作时，对于xi，先计算 xi mod 1000000007，即 qi/pi mod 1000000007 再进行求和可解。

最后，输出 total+s0。