提出 #69691455

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using u32 = uint32_t;
using namespace atcoder;

vector<u32> primes; // M の素因数
struct Modint {
    modint x; // M と互いに素な部分
    array<int, 9> pc; // pc[i] := primes[i] が何個掛けられているか？
    Modint() {}
    Modint(u32 a): pc{} {
        assert(a > 0);
        for (u32 i = 0; i < size(primes); i++) {
            const u32 p = primes[i];
            while (a % p == 0) {
                a /= p;
                pc[i]++;
            }
        }
        x = a;
    }
    Modint& operator*=(const Modint& rhs) {
        x *= rhs.x;
        for (u32 i = 0; i < size(primes); i++) {
            pc[i] += rhs.pc[i];
        }
        return *this;
    }
    friend Modint operator*(const Modint& lhs, const Modint& rhs) {
        return Modint(lhs) *= rhs;
    }
    Modint inv() const {
        Modint res = *this;
        res.x = x.inv();
        for (int& c : res.pc) c = -c;
        return res;
    }
    u32 val() const {
        auto v = x;
        for (u32 i = 0; i < size(primes); i++) {
            const modint p = primes[i];
            int c = pc[i];
            assert(c >= 0);
            while (c--) {
                auto v2 = v * p;
                if (v == v2) break;
                v = v2;
            }
        }
        return v.val();
    }
};
constexpr u32 MAX = 5000;
Modint fac[MAX + 1], inv[MAX + 1];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    
    u32 T, M;
    cin >> T >> M;
    modint::set_mod(M);
    
    // primes := (M の素因数) を計算
    for (u32 p = 2; p * p <= M; p++) {
        if (M % p == 0) {
            primes.push_back(p);
            do M /= p;
            while (M % p == 0);
        }
    }
    if (M > 1) primes.push_back(M);
    
    // 階乗前計算
    fac[0] = 1;
    for (u32 i = 1; i <= MAX; i++) fac[i] = fac[i - 1] * Modint(i);
    inv[MAX] = fac[MAX].inv();
    for (u32 i = MAX; i >= 1; i--) inv[i - 1] = inv[i] * Modint(i);
    
    // 答えの計算
    while (T--) {
        u32 N;
        cin >> N;
        Modint ans = 1;
        u32 sumC = 0;
        while (N--) {
            u32 C;
            cin >> C;
            ans *= inv[C];
            sumC += C;
        }
        ans *= fac[sumC];
        cout << ans.val() << '\n';
    }
}

提出情報

ジャッジ結果