[Luogu 3414]SAC#1 - 组合数

2021-05-05 18:32

阅读：703

标签：class desc ring blog des hint ace amp 偶数

Description

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

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

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

Input

输入仅包含一个整数n。

Output

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

Sample Input

Sample Output

Hint

对于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$式。

 1 #include 2 #include 3 #include
 4 #include 5 using namespace std;
 6 typedef long long lol;
 7 lol n,Mod=6662333;
 8 lol qpow(lol x,lol y)
 9 {
10   lol res=1;
11   while (y)
12     {
13       if (y&1) res=res*x%Mod;
14       x=x*x%Mod;
15       y=y/2;
16     }
17   return res;
18 }
19 int main()
20 {
21   cin>>n;
22   printf("%lld\n",qpow(2,n-1));
23 }

[Luogu 3414]SAC#1 - 组合数

标签：class desc ring blog des hint ace amp 偶数

原文地址：http://www.cnblogs.com/Y-E-T-I/p/7679210.html

上一篇：C#中委托的理解

下一篇：pixhawk原生固件在Windows下环境搭建笔记

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

亲，登录后才可以留言！

[Luogu 3414]SAC#1 - 组合数

Description

Input

Output

Sample Input

Sample Output

Hint

评论

热门文章

推荐文章

最新文章

置顶文章