题目链接:组合
题意:输入n, m, p,输出C(n,m)%p。
题解:
Lucas的定理,定理描述是,如果p是质数
那么得到
这样然后分别求,采用逆元计算即可。
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back typedef long long ll; const int maxint = 0x7fffffff; const ll maxll = 1LL<<60; int n, m, p; int quick_mod(ll a, ll b) { ll ans = 1; a %= p; while(b) { if(b & 1) { ans = ans * a % p; b--; } b >>= 1; a = a * a % p; } return ans; } int Lucas(int n, int m){ ll ans = 1; if( m > n ) return 0; for(int i = 1; i <= m; i ++){ ll a = (n+i-m) % p; ll b = i%p; ans = ans*(a*quick_mod(b, p-2)%p)%p; } return ans; } int main(){ int t; cin >> t; while(t--){ cin >> n >> m >> p; cout << Lucas(n, m) << endl; } return 0; }