题解求和式 S(n) 的组合化简与模运算

lyx9197772026-06-102026-06-10

题解

OIer们好！这道题要求我们计算一个包含组合数和分数的复杂求和式：

$S(n) = \sum\\\_{k=0}^{n} \binom{n}{k} \frac{2^k}{k+1}$

并且要求结果对 $998244353$ 取模。

如果直接按照公式一步步算，不仅会超时，还会遇到一个巨大的麻烦：在取模的世界里，分数怎么算？

别担心，这篇题解会带你从零开始，先搞懂”分数取模”这个魔法，然后再用两种不同的方法（微积分法和纯代数法）把复杂的式子化简，最后轻松写出代码！

第一部分：前置知识——分数取模（模意义下的除法）

在普通的数学里，$6 \div 2 = 3$。但是在取模（比如模 $7$）的世界里，我们只关心余数，没有小数。那 $6 \div 2 \pmod 7$ 怎么算呢？

1. 把”除法”变成”乘法”

在普通数学中，除以一个数，等于乘以它的倒数。比如 $6 \div 2 = 6 \times \frac{1}{2}$。
在取模的世界里，我们也找一个”倒数”，我们叫它 “乘法逆元”。
假设我们要算 $A \div B \pmod p$，我们可以把它变成 $A \times B^{-1} \pmod p$。这里的 $B^{-1}$ 就是 $B$ 在模 $p$ 意义下的”倒数”。

什么是”倒数”呢？
在普通数学里，$2 \times \frac{1}{2} = 1$。
在取模世界里，$B$ 的”倒数” $B^{-1}$ 必须满足：

$B \times B^{-1} \equiv 1 \pmod p$

2. 怎么找”倒数”（乘法逆元）？

这里我们要请出一个超级厉害的定理：费马小定理。
费马小定理说：如果 $p$ 是一个质数（比如 $998244353$），且 $B$ 不是 $p$ 的倍数，那么：

$B^{p-1} \equiv 1 \pmod p$

我们把 $B^{p-1}$ 拆成 $B \times B^{p-2}$，就变成了：

$B \times B^{p-2} \equiv 1 \pmod p$

对比刚才 $B \times B^{-1} \equiv 1 \pmod p$ 的定义，你是不是发现了什么？
没错！$B$ 的倒数（乘法逆元）就是 $B^{p-2}$！
也就是说：

$B^{-1} \equiv B^{p-2} \pmod p$

3. 举个简单的例子

假设我们要计算 $3 \div 2 \pmod 7$。这里 $p=7$。

先找 $2$ 的倒数：$2^{-1} \equiv 2^{7-2} = 2^5 = 32$。
$32$ 对 $7$ 取模：$32 \div 7 = 4 \dots 4$，所以 $2^{-1} \equiv 4 \pmod 7$。
把除法变乘法：$3 \div 2 \equiv 3 \times 4 = 12 \pmod 7$。
$12$ 对 $7$ 取模等于 $5$。
验证：在普通数学里 $3 \div 2 = 1.5$。在模 $7$ 下，$5 \times 2 = 10$，$10 \div 7 = 1 \dots 3$，余数确实是 $3$！魔法成功！

总结公式：

$\frac{A}{B} \pmod p \equiv A \times B^{p-2} \pmod p$

第二部分：解法一（积分构造法）

虽然同学们可能还没学过微积分，但我们可以把它想象成”求面积”。这个方法非常巧妙，能把复杂的求和变成简单的公式。

引理 1：分式的面积表示

命题：对于任意非负整数 $k$，有 $\frac{1}{k+1} = \int_0^1 x^k \, dx$。
证明：
在微积分中，求函数 $x^k$ 从 $0$ 到 $1$ 的定积分（也就是曲线下的面积），规则是把指数加 $1$，再除以新的指数。

$\int\\\_0^1 x^k \, dx = \left[ \frac{x^{k+1}}{k+1} \right]\\\_0^1$

把上限 $1$ 和下限 $0$ 代入：

$\frac{1^{k+1}}{k+1} - \frac{0^{k+1}}{k+1} = \frac{1}{k+1} - 0 = \frac{1}{k+1}$

证明完毕。

引理 2：求和与积分可以交换顺序

命题：先加再求面积，等于先求面积再加。即 $\sum \int = \int \sum$。
证明：
积分（求面积）具有”线性”性质。就像你算几个长方形总面积，可以先算每个的面积再相加，也可以把它们拼成一个大图形再算总面积，结果是一样的。

步骤 1：把原式变成积分

根据引理 1，我们把原式中的 $\frac{1}{k+1}$ 替换成 $\int_0^1 x^k \, dx$：

$S(n) = \sum\\\_{k=0}^{n} \binom{n}{k} 2^k \int\\\_0^1 x^k \, dx$

根据引理 2，我们把求和符号 $\sum$ 移到积分号 $\int$ 里面去：

$S(n) = \int\\\_0^1 \left( \sum\\\_{k=0}^{n} \binom{n}{k} 2^k x^k \right) dx$

把 $2$ 和 $x$ 乘起来，变成 $(2x)^k$：

$S(n) = \int\\\_0^1 \left( \sum\\\_{k=0}^{n} \binom{n}{k} (2x)^k \right) dx$

引理 3：二项式定理

命题：$\sum_{k=0}^{n} \binom{n}{k} y^k = (1+y)^n$。
证明：
我们用数学归纳法。

当 $n=0$ 时，左边 $= \binom{0}{0}y^0 = 1$，右边 $= (1+y)^0 = 1$，成立。
假设 $n=m$ 时成立。当 $n=m+1$ 时： $(1+y)^{m+1} = (1+y)(1+y)^m = (1+y) \sum\\\_{k=0}^m \binom{m}{k} y^k$ 展开后，利用杨辉三角的性质 $\binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}$，刚好可以凑成 $\sum_{k=0}^{m+1} \binom{m+1}{k} y^k$。
证明完毕。

步骤 2：计算最终的积分

在引理 3 中，令 $y = 2x$，括号里的求和就变成了 $(1+2x)^n$。此时我们需要计算定积分：

$S(n) = \int\\\_0^1 (1+2x)^n \, dx$

为了准确计算出结果，我们使用换元法（这是处理此类积分最标准的方法）：

设新变量：令 $u = 1+2x$。
微分变换：对两边求导得 $du = 2dx$，即 $dx = \frac{1}{2}du$。

注意：这里的 $\frac{1}{2}$ 就是最终公式分母中那个 $2$ 的来源！
变换上下限：
- 当 $x=0$ 时，$u = 1+2(0) = 1$；
- 当 $x=1$ 时，$u = 1+2(1) = 3$。

将上述变换代入积分式：

$S(n) = \int\\\_1^3 u^n \cdot \frac{1}{2} \, du = \frac{1}{2} \int\\\_1^3 u^n \, du$

利用幂函数积分公式 $\int u^n du = \frac{u^{n+1}}{n+1}$：

$S(n) = \frac{1}{2} \left[ \frac{u^{n+1}}{n+1} \right]\\\_1^3 = \left[ \frac{u^{n+1}}{2(n+1)} \right]\\\_1^3$

最后代入上下限相减：

$S(n) = \frac{3^{n+1}}{2(n+1)} - \frac{1^{n+1}}{2(n+1)} = \frac{3^{n+1} - 1}{2(n+1)}$

太棒了！复杂的求和变成了一个超级简单的公式！

第三部分：解法二（组合恒等式法）

如果觉得积分太抽象，我们完全可以用纯代数的方法，通过变形组合数来得到同样的结果。

引理 4：组合数吸收恒等式

命题：$\frac{1}{k+1} \binom{n}{k} = \frac{1}{n+1} \binom{n+1}{k+1}$。
证明：
我们把组合数写成阶乘的形式 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。
左边：

$\frac{1}{k+1} \binom{n}{k} = \frac{1}{k+1} \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k+1)!(n-k)!}$

为了凑出右边的 $\binom{n+1}{k+1}$，我们在分子分母同时乘上 $(n+1)$：

$\frac{n!}{(k+1)!(n-k)!} = \frac{1}{n+1} \cdot \frac{(n+1)!}{(k+1)!((n+1)-(k+1))!} = \frac{1}{n+1} \binom{n+1}{k+1}$

左边等于右边，证明完毕。

步骤 1：代入并换元

把引理 4 代入原式：

$S(n) = \sum\\\_{k=0}^{n} \frac{1}{n+1} \binom{n+1}{k+1} 2^k$

把常数 $\frac{1}{n+1}$ 提到求和符号外面。为了让下标更整齐，我们令 $j = k+1$。当 $k$ 从 $0$ 变到 $n$ 时，$j$ 就从 $1$ 变到 $n+1$。同时 $2^k = 2^{j-1}$：

$S(n) = \frac{1}{n+1} \sum\\\_{j=1}^{n+1} \binom{n+1}{j} 2^{j-1}$

把 $2^{j-1}$ 拆成 $\frac{2^j}{2}$，再把 $\frac{1}{2}$ 提出来：

$S(n) = \frac{1}{2(n+1)} \sum\\\_{j=1}^{n+1} \binom{n+1}{j} 2^j$

引理 5：二项式展开的截断求和

命题：$\sum_{j=1}^{n+1} \binom{n+1}{j} 2^j = 3^{n+1} - 1$。

详细证明：

我们要计算的是从 $j=1$ 开始到 $n+1$ 的和。但是，我们熟悉的二项式定理（引理 3）给出的公式是从 $j=0$ 开始的完整展开式。

回顾完整的二项式展开：
根据引理 3，对于任意 $y$ 和整数 $m$，有 $\sum_{j=0}^{m} \binom{m}{j} y^j = (1+y)^m$。

在本题中，令 $m = n+1$，$y = 2$。代入公式得：
$\sum\\\_{j=0}^{n+1} \binom{n+1}{j} 2^j = (1+2)^{n+1} = 3^{n+1}$
这个等式左边包含了从 $j=0$ 到 $j=n+1$ 的所有项。
拆分求和项：
我们可以把左边的求和拆成两部分：第一项（$j=0$） 和 剩余项（$j=1$ 到 $n+1$）。
$\underbrace{\binom{n+1}{0} 2^0}\\\_{j=0 \text{ 的项}} + \underbrace{\sum\\\_{j=1}^{n+1} \binom{n+1}{j} 2^j}\\\_{\text{我们要求的部分}} = 3^{n+1}$
计算第一项的值：
- 组合数性质：任何数的 0 次组合数都为 1，即 $\binom{n+1}{0} = 1$。
- 指数性质：任何非零数的 0 次方都为 1，即 $2^0 = 1$。
- 所以，第一项 $\binom{n+1}{0} 2^0 = 1 \times 1 = 1$。
移项得出结果：
将计算好的第一项代回等式：
$1 + \sum\\\_{j=1}^{n+1} \binom{n+1}{j} 2^j = 3^{n+1}$
为了求出我们需要的求和部分，我们将左边的 $1$ 移到等式右边（变成减 1）：
$\sum\\\_{j=1}^{n+1} \binom{n+1}{j} 2^j = 3^{n+1} - 1$

直观理解：
这就好比你有一堆糖果总数是 $3^{n+1}$ 颗。这堆糖果里包含了一个特殊的”第 0 号盒子”，里面正好有 1 颗糖。如果你想知道除了”第 0 号盒子”以外所有盒子里的糖果总数，只需要用总数减去那 1 颗糖即可。

证明完毕。

步骤 2：得出最终公式

把引理 5 的结果代入步骤 1 的式子中：

$S(n) = \frac{1}{2(n+1)} (3^{n+1} - 1) = \frac{3^{n+1} - 1}{2(n+1)}$

看！我们用纯代数的方法，也得到了完全一样的公式！

第四部分：算法实现与代码

现在我们有了最终公式：

$S(n) \equiv \frac{3^{n+1} - 1}{2(n+1)} \pmod{998244353}$

结合第一部分学的”分数取模”知识，我们可以这样写代码：

分子是 $3^{n+1} - 1$。用快速幂算出 $3^{n+1} \pmod{998244353}$，然后减 $1$。注意如果减 $1$ 后变成负数，要加上模数再取模。
分母是 $2(n+1)$。
根据费马小定理，分母的倒数（逆元）是 $(2(n+1))^{998244353-2} \pmod{998244353}$，同样用快速幂计算。
最后把分子和分母的逆元乘起来，再对 $998244353$ 取模。

C++ 代码实现

#include<bits/stdc++.h>

using namespace std;

const int MOD=998244353;

int t,n;

int ksm(int a,int b){
    int res=1;
    while(b>0){
        if(b&1){
            res=1LL*res*a%MOD;
        }
        a=1LL*a*a%MOD;
        b>>=1;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n;
        int num=(ksm(3,n+1)-1+MOD)%MOD;
        int den=2LL*(n+1)%MOD;
        int ans=1LL*num*ksm(den,MOD-2)%MOD;
        cout<<ans<<'\n';
    }
    return 0;
}

代码细节讲解及注意事项：

ios::sync_with_stdio(false); cin.tie(nullptr);：因为题目有多达 $10^6$ 次询问，输入输出量极大。这两行代码可以关闭 C++ 和 C 标准库的同步，大大加快 cin 和 cout 的速度，防止超时 ~~被老爷机肘飞~~。
1LL * res * a % MOD：在乘法前加上 1LL，是为了把 int 转换成 long long，防止两个接近 $10^9$ 的数相乘时超出 int 的最大范围（溢出）。虽然可以保证取模后不会超过int范围，但在计算过程中会出现溢出情况。
(ksm(3,n+1)-1+MOD)%MOD：如果 ksm 算出来是 $0$，减 $1$ 会变成 $-1$。在 C++ 中负数取模还是负数，所以我们要先加上一个 MOD，保证它是正数后再取模。

后记及贡献说明

本人造题时想的是方法一（积分），方法二为DeepSeek所创。 ~~类入一败涂地~~
引理证明部分采自知乎和《普林斯顿微积分读本（修订版）》（[美]阿德里安·班纳）。
数据生成器使用AtomCode Coding Plus编写（仅限in数据随机生成器），out为调用正解生成，保证正确性。
第一部分分数取模采自Qwen，本人已严格审查无误。
本文AI占比不超过25%。