传送门：点击打开链接
题意：求C(n,m)%p,其中n<=1e18,m<=1e18,p1*p2*....*pn<=1e18,pi<1e5
思路：这题出的非常好，也揭示了如何处理p不是质数的方案。可以用lucas求C(n,m) n<=1e18,m<=1e18,p<=1e5，然后得到n个模方程，再通过中国剩余定理合并模方程就行了，但是要注意一个地方，就是在使用中国剩余定理的时候，最后那个M可能会很大，所以乘法的时候可能会爆LL，要用快速乘去处理
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 10 + 5;LL multi(LL a, LL b, LL p) {LL ret = 0;while(b) {if(b & 1) ret = (ret + a) % p;a = (a + a) % p;b >>= 1;}return ret;
}LL power(LL a, LL b, LL p) {LL res = 1;while(b != 0) {if(b & 1) res = (res * a) % p;a = (a * a) % p;b >>= 1;}return res;
}LL Comb(LL a, LL b, LL p) {if(a < b) return 0;if(a == b) return 1;if(b > a - b) b = a - b;LL ans = 1, ca = 1, cb = 1;for(LL i = 0; i < b; ++i) {ca = (ca * (a - i)) % p;cb = (cb * (b - i)) % p;}ans = (ca * power(cb, p - 2, p)) % p;return ans;
}LL Lucas(LL n, LL m, LL p) {LL ans = 1;while(n && m && ans) {ans = (ans * Comb(n % p, m % p, p)) % p;n /= p;m /= p;}return ans;
}LL exgcd(LL a, LL b, LL &x, LL &y) {if(b == 0) {x = 1; y = 0;return a;}LL r = exgcd(b, a % b, x, y);LL t = y;y = x - a / b * y;x = t;return r;
}/*x % m = a*/
LL china(int n, int *m, int *a) {LL M = 1, d, y, x = 0;for(int i = 0; i < n; i++) M *= m[i];for(int i = 0; i < n; i++) {LL w = M / m[i];d = exgcd(m[i], w, d, y);x = (x + multi(multi(y, w, M), a[i], M)) % M;}return (x + M) % M;
}int A[MX], B[MX];int main() {int T; //FIN;scanf("%d", &T);while(T--) {LL m, n, k;scanf("%I64d%I64d%I64d", &n, &m, &k);for(int i = 0; i < k; i++) {scanf("%d", &A[i]);B[i] = Lucas(n, m, A[i]);}printf("%I64d\n", china(k, A, B));}return 0;
}