信奥赛C++提高组csp-s之快速幂（案例实践3）
题目描述
今天小明学习了组合数，现在他很想知道
∑
C
n
i
\\sum \\rm{C}_{n}^{i}
∑Cni 是多少。其中
C
\\rm{C}
C 是组合数（即
C
n
i
\\rm{C}_{n}^{i}
Cni 表示
n
n
n 个物品无顺序选取
i
i
i 个的方案数），
i
i
i 取从
0
0
0 到
n
n
n 的所有偶数。
由于答案可能很大，请输出答案对
6662333
6662333
6662333 的余数。
输入格式
输入仅包含一个整数
n
n
n。
输出格式
输出一个整数，即为答案。
输入输出样例 1
输入 1
3
输出 1
4
说明/提示
对于
20
%
20\\%
20% 的数据，
n
≤
20
n \\le 20
n≤20；
对于
50
%
50\\%
50% 的数据，
n
≤
10
3
n \\le 10^{3}
n≤103；
对于
100
%
100\\%
100% 的数据，
n
≤
10
18
n \\le 10^{18}
n≤1018。
分析思路
题目要求计算组合数
C
n
i
\\mathrm{C}_n^i
Cni 中所有偶数
i
i
i 的和。利用二项式定理：
-
(
1
+
1
)
n
=
∑
i
=
0
n
C
n
i
=
2
n
(1+1)^n = \\sum_{i=0}^n \\mathrm{C}_n^i = 2^n
(1+1)n=∑i=0nCni=2n， -
(
1
−
1
)
n
=
∑
i
=
0
n
(
−
1
)
i
C
n
i
=
{
1
n
=
0
0
n
>
0
(1-1)^n = \\sum_{i=0}^n (-1)^i \\mathrm{C}_n^i = \\begin{cases} 1 & n=0 \\\\ 0 & n>0 \\end{cases}
(1−1)n=∑i=0n(−1)iCni={10n=0n>0。
两式相加得： $ 2\\sum_{i\\text{为偶数}} \\mathrm{C}_n^i = 2^n + (1-1)^n. $ 当
n
=
0
n=0
n=0 时，
(
1
−
1
)
0
=
1
(1-1)^0 = 1
(1−1)0=1，所以和为
1
1
1； 当
n
≥
1
n\\ge 1
n≥1 时，
(
1
−
1
)
n
=
0
(1-1)^n = 0
(1−1)n=0，所以和为
2
n
−
1
2^{n-1}
2n−1。
因此答案直接由
2
n
−
1
m
o
d
6662333
2^{n-1} \\bmod 6662333
2n−1mod6662333 给出（
n
≥
1
n\\ge 1
n≥1），
n
=
0
n=0
n=0 时输出
1
1
1。由于
n
n
n 最大可达
10
18
10^{18}
1018，需要用快速幂取模计算。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 定义长整型别名
const ll MOD = 6662333; // 题目给定的模数
// 快速幂函数：计算 (a^b) % mod
ll qpow(ll a, ll b, ll mod) {
ll res = 1; // 初始化结果为 1
a %= mod; // 先取模，防止溢出
while (b) { // 当指数不为0时循环
if (b & 1) // 如果当前二进制位为1
res = res * a % mod; // 累乘当前底数并取模
a = a * a % mod; // 底数平方并取模
b >>= 1; // 指数右移一位
}
return res; // 返回结果
}
int main() {
ll n;
cin >> n;
// 根据推导：n=0 时答案为 1，否则答案为 2^(n-1) mod MOD
if (n == 0) {
cout << 1 << endl;
} else {
cout << qpow(2, n – 1, MOD) << endl; // 快速幂计算
}
return 0;
}
功能分析
- 输入处理：读取一个整数
n
n
n，范围0
≤
n
≤
10
18
0 \\le n \\le 10^{18}
0≤n≤1018。 - 核心算法：利用组合数性质直接转化为
2
n
−
1
m
o
d
M
O
D
2^{n-1} \\bmod MOD
2n−1modMOD（n
≥
1
n\\ge 1
n≥1），使用快速幂在O
(
log
n
)
O(\\log n)
O(logn) 时间内完成计算。 - 边界处理：单独处理
n
=
0
n=0
n=0 的情况，输出1
1
1。 - 空间复杂度：仅使用常数个变量，
O
(
1
)
O(1)
O(1)。 - 正确性：推导基于二项式定理，数学上严格成立；快速幂算法保证大指数下的高效取模运算，结果与直接累加组合数一致（但后者无法处理
n
n
n 极大时的计算）。
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}
1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
