洛谷P3414 SAC#1 - 组合数

2021-04-30 21:27

阅读：440

标签：nav ima 输入输出 log ons div 答案 orange 今天

洛谷P3414 SAC#1 - 组合数

题目描述

辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！

今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少；其中C是组合数（即C(n,i)表示n个物品无顺序选取i个的方案数），i取从0到n所有偶数。

由于答案可能很大，请输出答案对6662333的余数。

输入输出格式

输入格式：

输入仅包含一个整数n。

输出格式：

输出一个整数，即为答案。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

对于20%的数据，n

对于50%的数据，n

对于100%的数据，n

分析

原文地址

1、

2、

3、

证明：由

当$a = b = 1$时，代入二项式定理可证明$1$式；

当$a = -1$，$b = 1$时代入二项式定理可证明$2$式；代入$a = 1$，$b = -1$可得到另一个意义相同的式子；

$(1式+2式) \over 2$可证明$3$式。

代码

又复习了一下二项式定理。

#includeusing namespace std;
const long long mo=6662333;
long long ksm(long long a,long long p){
    if(p0) return 0; long long res=1; a%=mo; //这儿要先对a取模
    for(;p;p>>=1,a=a*a%mo) if(p&1) res=res*a%mo;
    return res;
}
int main(){
    long long n; scanf("%lld",&n);
    printf("%lld",ksm(2,n-1));
    return 0;
}

洛谷P3414 SAC#1 - 组合数

标签：nav ima 输入输出 log ons div 答案 orange 今天

原文地址：http://www.cnblogs.com/huihao/p/7800655.html

上一篇：在Windows系统下搭建ELK日志分析平台

下一篇：使用canvas 的api 实现图片的显示及压缩

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：洛谷P3414 SAC#1 - 组合数
文章链接：http://soscw.com/index.php/essay/80563.html

亲，登录后才可以留言！

洛谷P3414 SAC#1 - 组合数

洛谷P3414 SAC#1 - 组合数

题目描述

输入输出格式

输入输出样例

说明

分析

代码

评论

热门文章

推荐文章

最新文章

置顶文章