问题 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 的答案。

样例输入

样例输出

思路：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;

}