首页 > 代码库 > P3414 SAC#1 - 组合数
P3414 SAC#1 - 组合数
题目背景
本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。
寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。
题目描述
辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!
今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少;其中C是组合数(即C(n,i)表示n个物品无顺序选取i个的方案数),i取从0到n所有偶数。
由于答案可能很大,请输出答案对6662333的余数。
输入输出格式
输入格式:
输入仅包含一个整数n。
输出格式:
输出一个整数,即为答案。
输入输出样例
输入样例#1:
3
输出样例#1:
4
说明
对于20%的数据,n <= 20;
对于50%的数据,n <= 1000;
对于100%的数据,n <= 1 000 000 000 000 000 000 (10^18)
/*(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)b+...+C(n,i)a^(n-i)b^i+...+C(n,n)b^n因为n只为偶数,就取一半及2^n-1次*/#include<cstdio>#include<iostream>using namespace std;typedef long long ll;const ll mod=6662333;int n,k;ll ans;ll fpow(ll a,ll p){ ll res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res;}int main(){ ll n;cin>>n; cout<<fpow(2,n-1); return 0;}
P3414 SAC#1 - 组合数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。