1656：Combination
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
原题来自：BZOJ 2982
LMZ 有 n 个不同的基友，他每天晚上要选 m 个进行 [河蟹]，而且要求每天晚上的选择都不一样。那么 LMZ 能够持续多少个这样的夜晚呢？当然，LMZ 的一年有 10007 天，所以他想知道答案 mod10007 的值。
【输入】
第一行一个整数 t，表示有 t 组数据；
接下来 t 行每行两个整数 n,m，如题意。
【输出】
t 行，每行一个数，为 (nm)mod10007的答案。
【输入样例】
4
5 1
5 2
7 3
4 2
【输出样例】
5
10
35
6
【提示】
数据范围与提示：
对于全部数据，1≤t≤200,1≤m≤n≤2×10 。
sol：日常跳出模板题。。
lucas模板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const ll Mod=;
const int N=;
int T;
ll Jiec[N],InvJiec[N];
inline ll Ksm(ll x,ll y)
{
ll ans=;
while(y)
{
if(y&) ans=ans*x%Mod;
x=x*x%Mod;
y>>=;
}
return ans;
}
inline ll C(ll n,ll m)
{
if(n<m) return ;
if(!InvJiec[m]) InvJiec[m]=Ksm(Jiec[m],Mod-);
if(!InvJiec[n-m]) InvJiec[n-m]=Ksm(Jiec[n-m],Mod-);
return Jiec[n]*InvJiec[m]%Mod*InvJiec[n-m]%Mod;
}
inline ll Lucas(ll n,ll m)
{
ll ans=;
while(n&&m)
{
ans=ans*C(n%Mod,m%Mod)%Mod;
n/=Mod;
m/=Mod;
}
return ans;
}
int main()
{
ll n,m,i;
Jiec[]=;
for(i=;i<=N-;i++)
{
Jiec[i]=Jiec[i-]*i%Mod;
}
R(T);
while(T--)
{
n=read(); m=read();
Wl(Lucas(n,m));
}
return ;
}
/*
input
4
5 1
5 2
7 3
4 2
output
5
10
35
6 input
1
591626 420684
output
4077
*/