Submission #49554632

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;

namespace MODINT_WITH_FIXED_MOD {
    constexpr valueType MOD = 998244353;

    template<typename T1, typename T2, typename T3 = valueType>
    void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
        a = a + b;

        if (a >= mod)
            a -= mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
        a = a - b;

        if (a < 0)
            a += mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
        return a + b >= mod ? a + b - mod : a + b;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
        return a - b < 0 ? a - b + mod : a - b;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
        return (long long) a * b % mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
        a = (long long) a * b % mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
        T1 result = 1;

        while (b > 0) {
            if (b & 1)
                Mul(result, a, mod);

            Mul(a, a, mod);
            b = b >> 1;
        }

        return result;
    }
} // namespace MODINT_WITH_FIXED_MOD

using namespace MODINT_WITH_FIXED_MOD;

class BinomialCoefficient {
private:
    valueType N;
    ValueVector _Fact, _InvFact;

public:
    BinomialCoefficient() = default;

    BinomialCoefficient(valueType n) : N(n), _Fact(N + 1, 1), _InvFact(N + 1, 1) {
        for (valueType i = 1; i <= N; ++i)
            _Fact[i] = mul(_Fact[i - 1], i);

        _InvFact[N] = pow(_Fact[N], MOD - 2);

        for (valueType i = N - 1; i >= 0; --i)
            _InvFact[i] = mul(_InvFact[i + 1], i + 1);
    }

    valueType operator()(valueType n, valueType m) {
        if (n < 0 || m < 0 || n < m)
            return 0;

        if (m > N)
            throw std::out_of_range("BinomialCoefficient::operator() : m > N");

        if (n <= N)
            return mul(_Fact[n], mul(_InvFact[m], _InvFact[n - m]));

        valueType result = 1;

        for (valueType i = 0; i < m; ++i)
            Mul(result, n - i);

        Mul(result, _InvFact[m]);

        return result;
    }

    valueType Fact(valueType n) {
        if (n < 0)
            return 0;

        if (n > N)
            throw std::out_of_range("BinomialCoefficient::Fact : n > N");

        return _Fact[n];
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ++M;

    BinomialCoefficient C(N + 10000);

    ValueVector Type(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> Type[i];

    ValueMatrix F(N + 1, ValueVector(N + 1, 0));

    F[0][0] = 1;

    for (valueType i = 1; i <= N; ++i) {
        if (Type[i] == 1) {
            for (valueType j = 1; j <= i && j <= M; ++j) {
                F[i][j] = F[i - 1][j - 1];
            }
        } else {
            for (valueType j = 1; j <= i && j <= M; ++j) {
                // 原来
                Inc(F[i][j], mul(F[i - 1][j], j));

                // 新增
                Inc(F[i][j], mul(F[i - 1][j - 1], M - j + 1 - 1));
            }
        }
    }

    valueType ans = 0;

    for (valueType i = 1; i <= M && i <= N; ++i)
        Inc(ans, F[N][i]);

    std::cout << ans << std::endl;

    return 0;
}

Submission Info

Judge Result