题解
易得答案为
$$ \sum_{i=1}^m\binom{n-\sum_{j=1}^{i-1}w_j}{\sum_{j=1}^iw_j} $$
扩展$\text{Lucas}$即可
代码
#include#include #include #include #define RG register#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);#define clear(x, y) memset(x, y, sizeof(x))#define int long longinline int read(){ int data = 0, w = 1; char ch = getchar(); while(ch != '-' && (!isdigit(ch))) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar(); return data * w;}inline int fastpow(int x, int y, int Mod){ int ans = 1; while(y) { if(y & 1) ans = 1ll * ans * x % Mod; x = 1ll * x * x % Mod, y >>= 1; } return ans;}void exgcd(int a, int b, int &d, int &x, int &y){ !b ? d = a, x = 1, y = 0 : (exgcd(b, a % b, d, y, x), y -= x * (a / b));}inline int Inv(int i, int Mod){ if(!i) return 0; int x, y, d, a = i, b = Mod; exgcd(a, b, d, x, y); x = (x % b + b) % b; if(!x) x += b; return x;}int mul(int n, int p, int k){ if(!n) return 1; int ans = 1; for(int i = 2; i <= k; i++) if(i % p) ans = ans * i % k; ans = fastpow(ans, n / k, k); for(int i = 2; i <= n % k; i++) if(i % p) ans = ans * i % k; return ans * mul(n / p, p, k) % k;}inline int C(int n, int m, int Mod, int p, int k){ if(m > n) return 0; int a = mul(n, p, k), b = mul(m, p, k), c = mul(n - m, p, k), _k = 0; for(int i = n; i; i /= p) _k += i / p; for(int i = m; i; i /= p) _k -= i / p; for(int i = n - m; i; i /= p) _k -= i / p; int ans = a * Inv(b, k) % k * Inv(c, k) % k * fastpow(p, _k, k) % k; return ans * (Mod / k) % Mod * Inv(Mod / k, k) % Mod;}int n, m, sum, Mod, ans = 1, a[20];signed main(){#ifndef ONLINE_JUDGE file(cpp);#endif Mod = read(), n = read(), m = read(); for(signed i = 1; i <= m; i++) sum += (a[i] = read()); if(sum > n) return puts("Impossible") & 0; for(signed k = 1; k <= m; k++) { n -= a[k - 1]; int now = 0, x = Mod; for(int i = 2; i * i <= Mod; i++) if(!(x % i)) { int _k = 1; while(!(x % i)) _k *= i, x /= i; now = (now + C(n, a[k], Mod, i, _k)) % Mod; } if(x > 1) now = (now + C(n, a[k], Mod, x, x)) % Mod; ans = ans * now % Mod; } printf("%lld\n", ans); return 0;}