【问题描述】
商店里出售n种不同品种的花。为了装饰桌面，你打算买m支花回家。你觉得放两支一样的花很难看，因此每种品种的花最多买1支。求总共有几种不同的买花的方案？答案可能很大，输出答案mod p的值。【输入格式】
一行3个整数n，m，p，意义如题所述。【输出格式】
一个整数，表示买花的方案数。 【输入输出样例1】 4 2 5 1 【输入输出样例1说明】 用数字1,2,3,4来表示花的种类的话，4种花里买各不相同的2支的方案有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(3,4)，共6种方案，模5后余数是1。【数据范围】
对于30%的数据，n,m≤10 对于50%的数据，n,m≤1000 对于80%的数据，1≤m≤n≤50,000 对于100%的数据，1≤m≤n≤1,000,000，p≤1,000,000,000n^2的杨辉三角肯定不行。
因为p不一定是质数，所以用费马小定理求逆元也不行。 只能用分解质因数。 数据很强，要用到快速幂，线性质数筛。 注意剪枝和利用开方降低时间复杂度。#include#include #include #include #define LL long longusing namespace std;LL n,m,p;LL ans;int num[1000009],prime[1000009],cnt;bool notp[1000009];void Prime(){ notp[0]=1,notp[1]=1; for(LL i=2;i<=n;i++) { if(!notp[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { notp[i*prime[j]]=1; if(i%prime[j]==0) break; } }}//线性筛素数LL Fast_pow(LL x,LL k){ LL a1=1; x%=p; while(k) { if(k%2) a1=a1*x%p; x=(x*x)%p; k/=2; } return a1;}void tear(LL x,int d){ LL r=(sqrt(x)+0.5); for(LL i=1;i<=cnt;i++) { if(!notp[x]) {num[x]+=d;return;} //剪枝 LL k=prime[i]; if(k>r) break;//剪枝 while(x%k==0) { num[k]+=d; x/=k; } } if(x>1) num[x]+=d;}void get_ans(){ ans=1; for(LL i=2;i<=n;i++) { if(num[i]) { ans=(ans*Fast_pow(i,num[i]))%p; } }}int main(){ //freopen("flower.in","r",stdin); //freopen("flower.out","w",stdout); scanf("%lld%lld%lld",&n,&m,&p); Prime(); for(LL i=m+1;i<=n;i++) tear(i,1); for(LL i=2;i<=n-m;i++) tear(i,-1); get_ans(); printf("%lld",ans); return 0;}