问题 F: Combination
问题 F: Combination
时间限制: 1 Sec 内存限制: 128 MB
提交: 18 解决: 10
[提交][状态][讨论版][命题人:150112200121][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1705&pid=5
题目描述
LMZ 有 n 个不同的基友，他每天晚上要选 m 个进行 [河蟹]，而且要求每天晚上的选择都不一样。那么 LMZ 能够持续多少个这样的夜晚呢？当然，LMZ 的一年有 10007 天，所以他想知道答案 mod10007 的值。
输入
第一行一个整数 t，表示有 t 组数据；
接下来 t 行每行两个整数 n,m，如题意。
对于全部数据，1≤t≤200,1≤m≤n≤2×108。
输出
t 行，每行一个数，为(mn)mod10007 的答案。
样例输入
4
5 1
5 2
7 3
4 2 样例输出
5
10
35
6 思路：Lucas定理直接套
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b) { x = 1; y = 0; return a; }
ll res = exgcd(b, a%b, x, y), t;
t = x; x = y; y = t - a / b * y;
return res;
}
ll p;
inline ll power(ll a, ll b, ll mod)
{
ll sm;
for (sm = 1; b; b >>= 1, a = a * a%mod)if (b & 1)
sm = sm * a%mod;
return sm;
}
ll fac(ll n, ll pi, ll pk)
{
if (!n)return 1;
ll res = 1;
for (register ll i = 2; i <= pk; ++i)
if (i%pi)(res *= i) %= pk;
res = power(res, n / pk, pk);
for (register ll i = 2; i <= n % pk; ++i)
if (i%pi)(res *= i) %= pk;
return res * fac(n / pi, pi, pk) % pk;
}
inline ll inv(ll n, ll mod)
{
ll x, y;
exgcd(n, mod, x, y);
return (x += mod) > mod ? x - mod : x;
}
inline ll CRT(ll b, ll mod) { return b * inv(p / mod, mod) % p*(p / mod) % p; }
const int MAXN = 11;
static ll n, m;
static ll w[MAXN];
inline ll C(ll n, ll m, ll pi, ll pk)
{
ll up = fac(n, pi, pk), d1 = fac(m, pi, pk), d2 = fac(n - m, pi, pk);
ll k = 0;
for (register ll i = n; i; i /= pi)k += i / pi;
for (register ll i = m; i; i /= pi)k -= i / pi;
for (register ll i = n - m; i; i /= pi)k -= i / pi;
return up * inv(d1, pk) % pk*inv(d2, pk) % pk*power(pi, k, pk) % pk;
}
inline ll exlucus(ll n, ll m)
{
ll res = 0, tmp = p, pk;
static int lim = sqrt(p) + 5;
for (register int i = 2; i <= lim; ++i)if (tmp%i == 0)
{
pk = 1; while (tmp%i == 0)pk *= i, tmp /= i;
(res += CRT(C(n, m, i, pk), pk)) %= p;
}
if (tmp > 1)(res += CRT(C(n, m, tmp, tmp), tmp)) %= p;
return res;
}
int main()
{
int t;
cin >> t;
p = 10007;
while (t--)
{
cin >> n >> m;
printf("%d\n", exlucus(n, m));
}
return 0;
}
