To be better

题解 P2183 【[国家集训队]礼物】

2018-09-27 16:04:54


看上去我的式子和别人的不一样所以我就来水一波233

我是这样考虑的:

对于这几个礼物,我们可以枚举排列,然后前 $w_1$ 个给第一个人,之后的 $w_2$ 个给第二个人……但是这样会有重复的,即有可能某个人拿的礼物的顺序不一样但是本质是相同的,这样的话,就要再除以 $w_i!$ ,不要忘了剩下没分的那部分也有重的,所以最后的式子就是 $\dfrac{n!}{(n-tot)!w_1!w_2!w_3!w_4!w_5!}$ 。

这样运用扩展lucas的思想就可以算了。

#include <cstdio>
#include <cmath>

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;
}