求解f(S)模运算

Question

设 S = {1,2,3,..., n}, 令 f(S) 表示所有 S 的非空子集和的平方和, 即:

$f(S) = \sum_{T \subseteq S, T \neq \emptyset} (\sum_{x \in T} x)^2$

求当 n = 2023 时, f(S) mod (10^9 + 7) 的值。

尝试编写一个python程序解决这个问题

Answer 1

下面给出了一种可行的思路和相应的 Python 实现。直接对 $2^n$ 个子集逐一计算在 $n=2023$ 时显然不可行（数量过于庞大），必须寻找一个更简洁的数学表达式并利用模运算技巧实现。

数学推导

令 $S = \{1,2,3,\dots,n\}$ 。我们要计算

f(S) \;=\; \sum_{\substack{T \subseteq S \\ T \neq \emptyset}} \Bigl(\sum_{x\in T} x\Bigr)^2.

将平方展开，可写为

\Bigl(\sum_{x\in T} x\Bigr)^2 \;=\; \sum_{x\in T} x^2 \;+\; 2\sum_{\substack{x,y\in T\\x<y}} x\,y.

因此

f(S) = \sum_{T \neq \emptyset}\sum_{x\in T} x^2 \;+\; 2 \sum_{T \neq \emptyset}\sum_{x<y,\;x,y\in T} x\,y.

第一部分： $\sum_{T \neq \emptyset}\sum_{x\in T} x^2$

对集合 $S$ 的所有非空子集求和，固定某个 $x\in S$ ，考虑它在多少个子集中出现：

集合 $S$ 的所有子集总数是 $2^n$ ；
包含固定元素 $x$ 的子集数为 $2^{n-1}$ ；
其中空集不包含任何元素，但这不影响“包含 $x$ ”的子集个数，仍是 $2^{n-1}$ 。

因此，每个 $x^2$ 会在 $2^{n-1}$ 个子集中出现，故

\sum_{T \neq \emptyset}\sum_{x\in T} x^2 \;=\; \sum_{x=1}^{n} x^2 \cdot 2^{n-1} \;=\; 2^{n-1}\,\sum_{x=1}^{n} x^2.

而

\sum_{x=1}^{n} x^2 \;=\; \frac{n(n+1)(2n+1)}{6}.

第二部分： $\sum_{T \neq \emptyset}\sum_{x<y} x\,y$

同理，固定 $x<y$ 后， $\{x,y\}$ 出现在多少个子集里？

只要子集同时包含 $x$ 和 $y$ ，那么其它 $n-2$ 个元素随意取或不取，共 $2^{n-2}$ 种；
不会重复计算空集，因为一旦固定 $x$ 和 $y$ ，子集就不可能是空的。

因此

\sum_{T \neq \emptyset} \sum_{x<y} x\,y \;=\; \sum_{x<y} \bigl(x\,y \cdot 2^{n-2}\bigr) \;=\; 2^{n-2}\,\sum_{1 \le x < y \le n} x\,y.

而

\sum_{1 \le x < y \le n} x\,y \;=\;\frac12\Bigl(\bigl(\sum_{i=1}^n i\bigr)^2 - \sum_{i=1}^n i^2\Bigr),

其中 $\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}.$

再带回去并加上前面那个系数 2（因为展开里有 $2\sum_{x<y}x\,y$ ）：

2 \sum_{T \neq \emptyset}\sum_{x<y} x\,y \;=\; 2\cdot 2^{n-2}\,\sum_{x<y} x\,y \;=\; 2^{n-1}\,\sum_{x<y} x\,y.

合并结果

把两部分加起来可得

f(S) \;=\; 2^{n-1}\sum_{x=1}^n x^2 \;+\; 2^{n-1}\sum_{x<y} x\,y \;=\; 2^{n-1} \Bigl[ \sum_{x=1}^n x^2 \;+\; \sum_{x<y} x\,y \Bigr].

而

\sum_{x<y} x\,y = \frac12 \Bigl[\Bigl(\sum_{i=1}^n i\Bigr)^2 - \sum_{i=1}^n i^2\Bigr].

将 $\sum_{i=1}^n i^2$ 与 $\bigl(\sum_{i=1}^n i\bigr)^2$ 合并，最终可以化简为一个较紧凑的形式：

f(S) \;=\; 2^{n-2} \Bigl[ \sum_{x=1}^n x^2 \;+\; \Bigl(\sum_{x=1}^n x\Bigr)^2 \Bigr] \;=\; 2^{n-2}\;\cdot\;\frac{n\,\bigl(n+1\bigr)\,\bigl(3n+1\bigr)\,\bigl(n+2\bigr)}{12}.

因此只要在模 $10^9+7$ 下依次完成

计算上述分子 $n(n+1)(3n+1)(n+2)$ ；
乘上 $12$ 在模下的乘法逆元；
再乘上 $2^{\,n-2}\bigr)\bmod(10^9+7)$ ；
最后取模即可。

Python 实现

下面是一段示例代码，演示如何在 Python 下进行大数模运算并得到结果。只需注意在每一步都对中间值取模，以免溢出或速度过慢。

python
def f_n_mod(n, MOD=10**9+7):
    # 1. 计算分子: n*(n+1)*(3n+1)*(n+2)，并取模
    numerator = n * (n+1) % MOD
    numerator = numerator * (3*n + 1) % MOD
    numerator = numerator * (n+2) % MOD
    
    # 2. 乘上 12 的乘法逆元 (即 12^{-1} mod MOD)
    #   根据费马小定理，若 MOD 为素数，则 a^{-1} = a^{MOD-2} (mod MOD)
    inv12 = pow(12, MOD-2, MOD)
    val = numerator * inv12 % MOD
    
    # 3. 计算 2^(n-2) (mod MOD)
    #   如果 n >= 2 才这样乘；若 n=1，理论上需要特殊判断，不过此题 n=2023
    power_2 = pow(2, n-2, MOD)
    
    # 4. 整体相乘取模
    return val * power_2 % MOD

if __name__ == "__main__":
    n = 2023
    MOD = 10**9 + 7
    ans = f_n_mod(n, MOD)
    print(ans)

只要运行这段程序，就可以得到

f(\{1,2,\dots,2023\}) \bmod (10^9+7)

的数值结果。

备注: 如果你想验证更小的 $n$ 是否正确，可以写一个「暴力+验公式」的双重检查代码，先在小 $n$ 下用子集遍历做校验，再用上面公式比对，确认无误后再跑大 $n$ 。

这样就完成了对题目的求解。核心是先利用组合/计数思想把看似对 $2^n$ 个子集的求和问题化为一个只含幂和简单多项式的表达式，然后在大数模下实现。运行上述代码即可得到最终答案。

Answer 2

程序执行结果为：

当 $n = 2023$ 时， $f(S) \mod (10^9 + 7) = 763183190$ 。

求解f(S)模运算

问题

思考

回答

数学推导

第一部分： $\sum_{T \neq \emptyset}\sum_{x\in T} x^2$

第二部分： $\sum_{T \neq \emptyset}\sum_{x<y} x\,y$

合并结果

Python 实现

问题

回答

分享这个问答

问题

思考

回答

数学推导

第一部分：∑T≠∅∑x∈Tx2\sum_{T \neq \emptyset}\sum_{x\in T} x^2∑T=∅​∑x∈T​x2

第二部分：∑T≠∅∑x<yx y\sum_{T \neq \emptyset}\sum_{x<y} x\,y∑T=∅​∑x<y​xy

合并结果

Python 实现

问题

回答

分享这个问答

第一部分： $\sum_{T \neq \emptyset}\sum_{x\in T} x^2$

第二部分： $\sum_{T \neq \emptyset}\sum_{x<y} x\,y$