Submission #50457769

---

Source Code Expand

#include<iostream>
#include<map>
#include<vector>
struct mint{
    static constexpr int  m = 998244353;
    int x;
    mint() : x(0){}
    mint(long long x_):x(x_ % m){if (x < 0) x += m;}
    int val(){return x;}
    mint &operator+=(mint b){if ((x += b.x) >= m) x -= m; return *this;}
    mint &operator-=(mint b){if ((x -= b.x) < 0) x += m; return *this;}
    mint &operator*=(mint b){x= (long long)(x) * b.x % m; return *this;}
    mint pow(long long e) const {
        mint r = 1,b =*this;
        while (e){
            if (e & 1) r *= b;
            b *= b;
            e >>= 1;
        }
        return r;
    }
    mint inv(){return pow(m - 2);}
    mint &operator/=(mint b){return *this *= b.pow(m - 2);}
    friend mint operator+(mint a, mint b){return a += b;}
    friend mint operator-(mint a, mint b){return a -= b;}
    friend mint operator/(mint a, mint b){return a /= b;}
    friend mint operator*(mint a, mint b){return a *= b;}
    friend bool operator==(mint a, mint b){return a.x == b.x;}
    friend bool operator!=(mint a, mint b){return a.x != b.x;}
};


namespace po167{
template<class T>
struct Binomial{
    std::vector<T> fact_vec, fact_inv_vec;
    void extend(int m = -1){
        int n = fact_vec.size();
        if (m == -1) m = n * 2;
        if (n >= m) return;
        fact_vec.resize(m);
        fact_inv_vec.resize(m);
        for (int i = n; i < m; i++){
            fact_vec[i] = fact_vec[i - 1] * T(i);
        }
        fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
        for (int i = m - 1; i > n; i--){
            fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
        }
    }
    Binomial(int MAX = 2){
        fact_vec.resize(1, T(1));
        fact_inv_vec.resize(1, T(1));
        extend(MAX + 1);
    }

    T fact(int i){
        if (i < 0) return 0;
        while (int(fact_vec.size()) <= i) extend();
        return fact_vec[i];
    }
    T invfact(int i){
        if (i < 0) return 0;
        while (int(fact_inv_vec.size()) <= i) extend();
        return fact_inv_vec[i];
    }
    T C(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(b) * invfact(a - b);
    }
    T invC(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(b) * fact(a - b) *invfact(a);
    }
    T P(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(a - b);
    }
    T inv(int a){
        if (a < 0) return inv(-a) * T(-1);
        if (a == 0) return 1;
        return fact(a - 1) * invfact(a);
    }
};
}

int solve_arc146_e(int N, std::vector<int> A){
    po167::Binomial<mint> B(200200);
    std::map<std::pair<int, int>, mint> dp;
    dp[{0, 0}] = 1;
    for (int i = 0; i < N; i++){
        std::map<std::pair<int, int>, mint> n_dp;
        for (auto tmp: dp){
            int l_indeg = tmp.first.first;
            int l_outdeg = l_indeg;
            int t = tmp.first.second;
            if (t == 1) l_outdeg--;
            if (t == 2) l_outdeg++;
            if (l_indeg < 0 || l_outdeg < 0) continue;

            if (i != 0){
                // 連結性を保ち続ける
                if (l_indeg == 0 && t % 3 == 0) continue;

                // 同じ辺を区別しないようにする
                tmp.second *= B.invfact(l_indeg);
                tmp.second *= B.invfact(l_outdeg);
            }

            for (int k = 0; k < 4; k++) if ((k & t) == 0 ){
                int r_indeg = A[i] - l_indeg;
                int r_outdeg = A[i] - l_outdeg;
                if(k & 1) r_indeg--;
                if(k & 2) r_outdeg--;
                mint val = tmp.second;

                // 全域木の数だけ乗算する
                if ((k & 2) == 0){
                    if (t & 2) val *= l_outdeg;
                    else val *= r_outdeg;
                }

                // 自分の出次は相手の入次
                if (val != 0) n_dp[{r_outdeg, k + t}] += val;
            }
        }
        std::swap(dp, n_dp);
    }
    mint ans = dp[{0, 3}];

    // prod (outdeg - 1)!
    for (int i = 0; i < N; i++){
        ans *= B.fact(A[i] - 1);
    }
    return ans.val();
}

int main(){
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::cout << solve_arc146_e(N, A) << "\n";
}

Submission Info

Judge Result