//计算n!中素因子p的指数 int Cal(int x, int p) { int ans = 0; long long rec = p; while(x>=rec) { ans += x/rec; rec *= p; } return ans; }
//计算n的k次方对M取模,二分法 int Pow(long long n, int k, int MOD) { long long ans = 1; while(k) { if(k&1) { ans = (ans * n) % MOD; } n = (n * n) % MOD; k >>= 1; } return ans; }
//计算C(n,m) int Combination(int n, int m) { vector<int> prim = produce_prim_number(); long long ans = 1; int num; for(int i=0; i<prim.size() && prim[i]<=n; ++i) { num = Cal(n, prim[i]) - Cal(m, prim[i]) - Cal(n-m, prim[i]); ans = (ans * Pow(prim[i], num, MOD)) % MOD; } return ans; }
int main() { int n,m; while(~scanf("%d%d",&n,&m)) { n=m+n-2; printf("%d\n",Combination(n-2,m-2)); } return 0; }
方案 2 31ms
# include <iostream> # include <cstdio> # include <algorithm> # include <cmath> # include <cstring> using namespace std;