首页 > 代码库 > bzoj——2982: combination
bzoj——2982: combination
2982: combination
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 611 Solved: 368
[Submit][Status][Discuss]
Description
LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
Input
第一行一个整数t，表示有t组数据。(t<=200)
接下来t行每行两个整数n, m，如题意。
Output
T行，每行一个数，为C(n, m) mod 10007的答案。
Sample Input
4
5 1
5 2
7 3
4 2
5 1
5 2
7 3
4 2
Sample Output
5
10
35
6
10
35
6
思路：
卢卡斯定理裸题
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 10008#define ll long long #define mod 10007using namespace std;ll t,n,m,ans,f[N];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;}ll qpow(ll n,ll k){ ll res=1; while(k) { if(k&1) res=res*n%mod; n=n*n%mod; k>>=1; }return res;}ll c(ll n,ll m){ if(m>n) return 0; return f[n]*qpow(f[n-m]*f[m],mod-2)%mod;}ll lus(ll n,ll m){ if(m==0) return 1; return c(n%mod,m%mod)*lus(n/mod,m/mod)%mod;}int main(){ t=read();f[0]=1; for(int i=1;i<=mod;i++) f[i]=f[i-1]*i%mod; while(t--) { n=read(),m=read(); ans=lus(n,m); printf("%lld\n",ans); } return 0;}
bzoj——2982: combination
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。