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)
排列组合（卢卡斯定理）能得50分、、
n的范围太大，数组开不开，因此就不能用lus定理了，我们应该在找一种做法
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define N 1000000#define mod 6662333#define ll long longusing namespace std;int n,ans,jie[N];int read(){ ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f;}ll qpow(ll a,ll b,ll p){ ll res=; while(b) { ) res=res*a%p; a=a*a%p;b>>=; }return res;}ll C(ll n,ll m,ll p){ ; ,p)%p;}ll Lus(ll n,ll m,ll p){ ) ; return Lus(n/p,m/p,p)*C(n%p,m%p,p);}int main(){ n=read();jie[]=; ;i<=n;i++) jie[i]=1ll*jie[i-]*i%mod; ;i<=n;i+=) ans=(ans+Lus(n,i,mod))%mod; printf("%d",ans); ;}
50分卢卡斯定理
打表找规律
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define N 1000000#define mod 6662333#define ll long longusing namespace std;int n,ans,jie[N];int read(){ ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f;}ll qpow(ll a,ll b,ll p){ ll res=; while(b) { ) res=res*a%p; a=a*a%p;b>>=; }return res;}ll C(ll n,ll m,ll p){ ; ,p)%p;}ll Lus(ll n,ll m,ll p){ ) ; return Lus(n/p,m/p,p)*C(n%p,m%p,p);}int main(){ jie[]=; ;i<;i++) jie[i]=1ll*jie[i-]*i%mod; ;n<=;n++) { ans=; ;i<=n;i+=) ans=(ans+Lus(n,i,mod))%mod; printf("%d %d\n",n,ans); } ;}
表
我们可以发现，ans=2^(n-1)，因此用快速幂就可以搞定了
n输入的时候要用long long、、（老是RE。。。）
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define mod 6662333#define ll long longusing namespace std;long long n;int ans;ll read(){ ll x=,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f;}int qpow(int a,ll b,int p){ ; while(b) { ) res=1ll*res*a%p; a=1ll*a*a%p;b>>=; }return res;}int main(){ n=read(); ans=qpow(,n-,mod); printf("%d",ans); ;}
