标签：cst ace 规律 ring 技术分享 str src bsp col
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。
输出格式：
输出一个整数，即为答案。
输入输出样例
说明
对于20%的数据，n
对于50%的数据，n
对于100%的数据，n
排列组合（卢卡斯定理）能得50分、、
n的范围太大，数组开不开，因此就不能用lus定理了，我们应该在找一种做法
#include
#include
#include
#include
#define N 1000000
#define mod 6662333
#define ll long long
using namespace std;
int n,ans,jie[N];
int read()
{
int x=0,f=1; char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘) x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
ll qpow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;b>>=1;
}return res;
}
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
return jie[n]*qpow(1ll*jie[m]*jie[n-m]%p,p-2,p)%p;
}
ll Lus(ll n,ll m,ll p)
{
if(m==0) return 1;
return Lus(n/p,m/p,p)*C(n%p,m%p,p);
}
int main()
{
n=read();jie[0]=1;
for(int i=1;i)
jie[i]=1ll*jie[i-1]*i%mod;
for(int i=0;i2)
ans=(ans+Lus(n,i,mod))%mod;
printf("%d",ans);
return 0;
}
50分卢卡斯定理
打表找规律
#include
#include
#include
#include
#define N 1000000
#define mod 6662333
#define ll long long
using namespace std;
int n,ans,jie[N];
int read()
{
int x=0,f=1; char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘) x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
ll qpow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;b>>=1;
}return res;
}
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
return jie[n]*qpow(1ll*jie[m]*jie[n-m]%p,p-2,p)%p;
}
ll Lus(ll n,ll m,ll p)
{
if(m==0) return 1;
return Lus(n/p,m/p,p)*C(n%p,m%p,p);
}
int main()
{
jie[0]=1;
for(int i=1;i100;i++)
jie[i]=1ll*jie[i-1]*i%mod;
for(n=1;n20;n++)
{
ans=0;
for(int i=0;i2)
ans=(ans+Lus(n,i,mod))%mod;
printf("%d %d\n",n,ans);
}
return 0;
}
表
我们可以发现，ans=2^(n-1)，因此用快速幂就可以搞定了
n输入的时候要用long long、、（老是RE。。。）
#include
#include
#include
#include
#define mod 6662333
#define ll long long
using namespace std;
long long n;int ans;
ll read()
{
ll x=0,f=1; char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘) x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
int qpow(int a,ll b,int p)
{
int res=1;
while(b)
{
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p;b>>=1;
}return res;
}
int main()
{
n=read();
ans=qpow(2,n-1,mod);
printf("%d",ans);
return 0;
}
洛谷——P3414 SAC#1 - 组合数
标签：cst ace 规律 ring 技术分享 str src bsp col
原文地址：http://www.cnblogs.com/z360/p/7900468.html