问题 A: 组合

问题 A: 组合

时间限制: 1 Sec  内存限制: 128 MB
提交: 22  解决: 13
[提交][状态][讨论版][命题人:150112200121][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1705&pid=0

题目描述

给出组合数 C(n,m) 表示从 n 个元素中选出 m 个元素的方案数。例如 C(5,2)=10,C(4,2)=6。可是当 n,m 比较大的时候，C(n,m) 很大。于是 xiaobo 希望你输出C(n,m)modp 的值。

输入

输入数据第一行是一个正整数 T，表示数据组数；

接下来是 T 组数据，每组数据有 3 个正整数 n,m,p。

对于所有数据，T≤100，1≤m≤n≤109，m≤104，m<p<109，p 是素数。

输出

对于每组数据，输出一个正整数，表示 C(n,m)modp 的结果。

样例输入

2

5 2 3

5 2 61

样例输出

1

10

思路：Lucas定理模板直接套

代码：

#include <bits/stdc++.h>

    using namespace std;

#define ll long long

    ll n, m, p;

    ll KSM(ll a, ll b) {

         ll s = 1;

         while (b) {

             if (b & 1)

                  s = s * a % p;

             a = a * a % p;

             b >>= 1;

         }

         return s;

    }

    ll C(ll n, ll m) {

         if (m > n)

             return 0;

         ll a = 1, b = 1;

         for (ll i = n - m + 1; i <= n; i++) a = a * i % p;

         for (ll i = 2; i <= m; i++) b = b * i % p;

         return a * KSM(b, p - 2) % p;

    }

    ll Lucas(ll n, ll m) {

         int i, j;

         if (!m)

             return 1;

         else

             return (C(n % p, m % p) * Lucas(n / p, m / p)) % p;

    }

    int main() {

         int i, j, k, T;

         cin >> T;

         while (T--) {

             cin >> n >> m >> p;

             cout << Lucas(n, m) << endl;

         }

    }