信奥赛C++提高组csp-s之快速幂（案例实践3）
信奥赛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 nn个物品无顺序选取i ii个的方案数），i ii取从0 00到n nn的所有偶数。
由于答案可能很大，请输出答案对6662333 66623336662333的余数。
输入格式
输入仅包含一个整数n nn。
输出格式
输出一个整数，即为答案。
输入输出样例 1
输入 1
3输出 1
4说明/提示
对于20 % 20\%20%的数据，n ≤ 20 n \le 20n≤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^iCni中所有偶数i ii的和。利用二项式定理：
- ( 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=0n=0时，( 1 − 1 ) 0 = 1 (1-1)^0 = 1(1−1)0=1，所以和为1 11；
当n ≥ 1 n\ge 1n≥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 66623332n−1mod6662333给出（n ≥ 1 n\ge 1n≥1），n = 0 n=0n=0时输出1 11。由于n nn最大可达10 18 10^{18}1018，需要用快速幂取模计算。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;// 定义长整型别名constll MOD=6662333;// 题目给定的模数// 快速幂函数：计算 (a^b) % modllqpow(ll a,ll b,ll mod){ll res=1;// 初始化结果为 1a%=mod;// 先取模，防止溢出while(b){// 当指数不为0时循环if(b&1)// 如果当前二进制位为1res=res*a%mod;// 累乘当前底数并取模a=a*a%mod;// 底数平方并取模b>>=1;// 指数右移一位}returnres;// 返回结果}intmain(){ll n;cin>>n;// 根据推导：n=0 时答案为 1，否则答案为 2^(n-1) mod MODif(n==0){cout<<1<<endl;}else{cout<<qpow(2,n-1,MOD)<<endl;// 快速幂计算}return0;}功能分析
- 输入处理：读取一个整数n nn，范围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 MOD2n−1modMOD（n ≥ 1 n\ge 1n≥1），使用快速幂在O ( log n ) O(\log n)O(logn)时间内完成计算。
- 边界处理：单独处理n = 0 n=0n=0的情况，输出1 11。
- 空间复杂度：仅使用常数个变量，O ( 1 ) O(1)O(1)。
- 正确性：推导基于二项式定理，数学上严格成立；快速幂算法保证大指数下的高效取模运算，结果与直接累加组合数一致（但后者无法处理n nn极大时的计算）。
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}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>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}