计算∑i²·C(n,i)（0≤i≤n），1≤n≤1e18，1秒内求模1e9+7

First, we can simplify the sum using combinatorial identities to get a closed-form formula, which is essential given the huge value of n.

Deriving the Closed-Form Formula #

We start by breaking down (i^2) into (i(i-1) + i):
[
\sum_{i=0}^n i^2 \binom{n}{i} = \sum_{i=0}^n [i(i-1) + i] \binom{n}{i} = \sum_{i=0}^n i(i-1)\binom{n}{i} + \sum_{i=0}^n i\binom{n}{i}
]

Step 1: Compute (\sum_{i=0}^n i\binom{n}{i}) #

This is a well-known identity:
[
\sum_{i=0}^n i\binom{n}{i} = n \cdot 2^{n-1}
]

Step 2: Compute (\sum_{i=0}^n i(i-1)\binom{n}{i}) #

Using the identity (i(i-1)\binom{n}{i} = n(n-1)\binom{n-2}{i-2}), we can rewrite the sum as:
[
\sum_{i=2}^n n(n-1)\binom{n-2}{i-2} = n(n-1) \sum_{k=0}^{n-2} \binom{n-2}{k} = n(n-1) \cdot 2^{n-2}
]
(where (k = i-2))

Combine the Results #

Adding the two sums together:
[
n(n-1) \cdot 2^{n-2} + n \cdot 2^{n-1} = n \cdot 2^{n-2} [(n-1) + 2] = n(n+1) \cdot 2^{n-2}
]

This formula works for all (n \geq 1) (for (n=1), (2^{n-2} = 2^{-1}), which is the modular inverse of 2 modulo (10^9+7)).

Computing the Result Modulo (10^9+7) #

Since (n) can be up to (10^{18}), we need to compute each part efficiently using modular arithmetic:

1. Modular Reduction: Compute (n \mod MOD) and ((n+1) \mod MOD) (where (MOD = 10^9+7)).
2. Modular Exponentiation: Compute (2^{n-2} \mod MOD). For (n=1), (2^{-1} \mod MOD) is equivalent to (2^{MOD-2} \mod MOD) (by Fermat's Little Theorem, since MOD is prime). Python's built-in pow function can handle this efficiently even for huge exponents.
3. Combine Terms: Multiply the three parts together, taking modulo MOD at each step to prevent overflow.

Python Implementation #

MOD = 10**9 + 7

n = int(input())
a = n % MOD
b = (n + 1) % MOD
exponent = n - 2
pow_2 = pow(2, exponent, MOD)
result = (a * b) % MOD
result = (result * pow_2) % MOD
print(result)

Explanation #

• Modular Reduction: Reducing (n) and (n+1) modulo MOD ensures we work with small numbers that fit in standard data types.
• Efficient Exponentiation: The pow function uses exponentiation by squaring, which runs in (O(\log n)) time—perfect for handling (n=10^{18}) quickly.
• Handling (n=1): When (n=1), pow(2, -1, MOD) correctly returns the modular inverse of 2 (500000004), since Python supports negative exponents in pow when the base and modulus are coprime.

This approach will compute the result within the 1-second time limit even for the largest (n).

内容的提问来源于stack exchange，提问作者hzyu