Description

Solution

我们可以想象成把这\(n\)件物品排成一个排列，然后第1个人拿前\(w_1\)个，第2个人拿之后的\(w_2\)个，以此类推。由于每个人拿到的东西的是没有顺序的，还要在方案数上除掉\(w_i!\)，别忘了剩下的物品其实也是没有顺序的，也要除以它们的阶乘。所以答案就是\(\dfrac{n!}{(n - \sum_iw_i)!\prod_{i}w_i!}\)。

直接用扩展lucas的思路算就行。

Code

#include 
    
     #include 
     
      typedef long long LL;LL n, m, P;LL w[6], tot;void exgcd(LL a, LL b, LL &x, LL &y, LL &d) {    if (!b) {        d = a;        x = 1;        y = 0;    } else {        exgcd(b, a%b, y, x, d);        y -= a / b * x;    }}LL pow_mod(LL x, LL p, LL mod) {    LL ans = 1;    for (; p; p>>=1, x=x*x%mod) if (p&1) ans = ans * x % mod;    return ans;}LL fac(LL n, LL p, LL pk) {    if (!n) return 1;    LL ans = 1;    for (int i = 2; i <= pk; ++i) if (i%p) ans = ans * i % pk;    ans = pow_mod(ans, n/pk, pk);    for (int i = 2; i <= n%pk; ++i) if (i%p) ans = ans * i % pk;    return ans * fac(n/p, p, pk) % pk;}LL inv(LL n, LL mod) {    LL x, y, d;    exgcd(n, mod, x, y, d);    return (x%=mod) < 0 ? x+mod : x;}LL CRT(LL b, LL mod) {    return b*(P/mod)%P*inv(P/mod, mod)%P;}LL calc(LL x, LL p) {    LL k = 0;    for (; x; x /= p) k += x / p;    return k;}LL C(LL p, LL pk) {    LL u = fac(n, p, pk), d = inv(fac(n-tot, p, pk), pk);    for (int i = 1; i <= m; ++i) {        d = d * inv(fac(w[i], p, pk), pk) % pk;    }    LL k = 0;    k += calc(n, p);    k -= calc(n-tot, p);    for (int i = 1; i <= m; ++i) {        k -= calc(w[i], p);    }    return u * d % pk * pow_mod(p, k, pk) % pk;}void work() {    if (tot > n) {        puts("Impossible");        return;    }    LL ans = 0, tmp = P, pk;    LL lim = sqrt(P) + 5;    for (int i = 2; i <= lim; ++i) if (tmp % i == 0) {        pk = 1;        while (tmp % i == 0) pk*=i, tmp/=i;        ans = (ans + CRT(C(i, pk), pk)) % P;    }    if (tmp > 1) {        ans = (ans + CRT(C(tmp, tmp), tmp)) % P;    }    printf("%lld\n", ans);}int main() {    scanf("%lld%lld%lld", &P, &n, &m);    for (int i = 1; i <= m; ++i) scanf("%lld", &w[i]), tot += w[i];    work();    return 0;}
     
    

Note

其实还有一种等价的答案：\(\displaystyle{n\choose \sum_i w_i}\prod_i{\sum_{j=i}^nw_j\choose w_i}\)不过这样要算很多次lucas，比较麻烦，也会比较慢。