对于 50% 的数据，0≤n≤10000,0≤m≤1000,p=892371480,1≤T≤105
对于另外 50% 的数据，0≤n,m≤107,p=998244353,1≤T≤105
求组合数
太菜了，看到题都在想什么“哎呀n这么大分解质因数？？”结果一看数据组数就傻眼了
唉，脑子还是不够活啊
求多组组合数当然是求乘法逆元直接算咯
50%的话，由于p是一个合数，而1-n的阶乘中所有数都与p不互质，因此不能算逆元了。
用组合数递推：f[i][j] = f[i - 1][j] + f[i - 1][j - 1]
另50%，考虑求阶乘的逆元
我们先费马小定理或者exgcd求出n!的逆元，然后对于i!的逆元：
inv[i] = inv[i + 1] * (i + 1) % p
很显然吧
然后就可以快乐切掉了
我好菜啊qaq
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<iostream> using namespace std; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; typedef int mainint; #define int long long inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } #define clr(a) memset(a,0,sizeof(a)); const int maxn = 1e7 + 5; int N = 1e7; int fac[maxn],inv[maxn]; int f[10001][1001]; int mod; int power(int a,int b) { int ans = 1,res = a; while(b) { if(b & 1) (ans *= res) %= mod; (res *= res) %= mod; b >>= 1; } return ans; } mainint main() { int T = read(),p = read(); if(p == 892371480) { N = 10000; int M = 1000; f[0][0] = 0; f[1][0] = f[1][1] = 1; for(int i = 2;i <= N;i++) { f[i][0] = 1; for(int j = 1;j <= M;j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % p; } while(T--) { int n = read(),m = read(); if(n < m) printf("0 "); else printf("%lld ",f[n][m]); } return 0; } mod = p; fac[0] = 1; for(int i = 1;i <= N;i++) fac[i] = fac[i - 1] * i % mod; inv[N] = power(fac[N],mod - 2); for(int i = N - 1;i >= 1;i--) inv[i] = inv[i + 1] * (i + 1) % mod; inv[0] = 1; while(T--) { int n = read(),m = read(); if(n < m) {printf("0 "); continue;} printf("%lld ",fac[n] * inv[m] % mod * inv[n - m] % mod); } }