组合数取模（杨辉三角+Lucas定理+模合数）

2019-04-13 16:50发布

站内文章 / 模拟电子
11799 0 1740
/* (1) 1 <= m <= n <= 1000 和 1 <= p <= 10^9 ( p可以是任何数 ) 这个问题比较简单，组合数的计算可以靠 杨辉三角 ，那么由于和的范围小，直接两层循环即可。 */ long long C[maxn][maxn]; void Comb(int n, int m, int p){ memset(C, 0, sizeof(C)); C[0][0] = 1; for(int i = 0; i <= n; i++){ C[i][0] = C[i][i] = 1; for(int j = 1; j < i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % p; } }

/* 1 <= m <= n <= 10^18 和 2 <= p <= 10^5 (p 是素数) Lucas定理 */ long long mod_pow(long long n, long long k, long long p) { if (k == 0) return 1; if (k == 1) return n; long long ans = mod_pow(n * n % p, k>>1, p); if (k&1) ans = ans * n % p; return ans; } long long Comb(long long n, long long m, long long p) { if (m > n) return 0; m = min(m, n - m); long long zi = 1, mu = 1; for (long long i = 0; i < m; i++) { zi = zi * (n - i) % p; mu = mu * (i + 1) % p; } return zi * mod_pow(mu, p - 2, p) % p; } long long Lucas(long long n, long long m, long long p) { if (m == 0) return 1; return Comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p; } /* 非递归的快速幂取模 long long mod_pow(long long x, long long k, long long MOD) { long long ans = 1; while (k) { if (k&1) ans = ans * x % MOD; x = x * x % MOD; k >>= 1; } return ans; } */

/* 1 <= m,n <= 10^6 和 p <= 10^9 (p不一定是素数) */ #include #include #include using namespace std; const long long maxn = 500005; int prime[maxn]; // 第i个素数（从0开始计数） bool is_prime[maxn+1]; // is_prime[i]为true表示i是素数 int getprime(int n){ //返回值是n以内素数的个数 int p = 0; for(int i = 0; i <= n; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for(int i = 2; i <= n; i++){ if(is_prime[i]){ prime[p++] = i; for(int j = 2*i; j <= n; j += i) is_prime[j] = false; } } return p; } long long count(long long x, long long y){ long long ret = 0; while(x / y){ ret += x/y; x /= y; } return ret; } long long mod_pow(long long n, long long k, long long p) { if (k == 0) return 1; if (k == 1) return n; long long ans = mod_pow(n * n % p, k>>1, p); if (k&1) ans = ans * n % p; return ans; } long long solve(long long n, long long m, long long p){ long long ans = 1; for(long long i = 0; prime[i] <= n; i++){ long long cnt = count(n, prime[i]) - count(m, prime[i]) - count(n-m, prime[i]); ans = ans * mod_pow(prime[i], cnt, p) % p; if(ans == 0) break; } return ans; } // 打素数表的时候要注意， 最大的素数 要 大于 输入的n int main(){ long long n, m, p; getprime(maxn); while(scanf("%I64d%I64d%I64d",&n, &m, &p)!=EOF){ printf("%I64d ",solve(n, m, p)); } return 0; }


热门文章