【bzoj2982】combination

2019-04-13 21:39发布

站内文章 / 模拟电子
17925 0 1375
Lucas定理裸题。
设L(n,m)为模mod意义下的组合数。
则L(n,m)=L(n / mod,m / mod)∗(n%mod)∗(m%mod)%mod，其中/为整除符号，%为取模符号。
预处理出阶乘的模和阶乘的模的逆，直接计算。 #include #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) inline int rd() { char c = getchar(); while (!isdigit(c)) c = getchar() ; int x = c - '0'; while (isdigit(c = getchar())) x = x * 10 + c - '0'; return x; } const int mod = 10007; typedef int arr[mod + 10]; arr invF , fact; int n , m; inline int mul(int a , int b) { a *= b ; if (a >= mod) a %= mod ; return a ; } inline int Pow(int a , int b) { int t = 1; while (b) { if (b & 1) t = mul(t , a); a = mul(a , a) , b >>= 1; } return t; } void init() { fact[1] = 1; rep (i , 2 , mod - 1) fact[i] = mul(fact[i - 1] , i); invF[1] = 1; rep (i , 2 , mod - 1) invF[i] = mul(invF[i - 1] , Pow(i , mod - 2)); invF[0] = fact[0] = 1; } void input() { n = rd() , m = rd(); } inline int _C(int n , int m) { if (n < m) return 0; return mul(fact[n] , mul(invF[n - m] , invF[m])); } void solve() { int t = 1; while (m) { t = mul(t , _C(n % mod , m % mod)); n = n / mod , m = m / mod; } printf("%d " , t); } int main() { #ifndef ONLINE_JUDGE // freopen("data.txt" , "r" , stdin); #endif init(); per (T , rd() , 1) { input(); solve(); } return 0; }

热门文章