提出 #71169648

---

ソースコード 拡げる

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

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

    string S;

    std::cin >> S;

    valueType const N = S.size();

    ValueVector Prefix(10), Suffix(10);

    for (valueType i = 1; i < N; ++i)
        ++Suffix[S[i] - '0'];

    ValueVector Fact(2 * N + 1, 1), InvFact(2 * N + 1, 1);
    for (valueType i = 1; i <= 2 * N; ++i)
        Fact[i] = mul(Fact[i - 1], i);

    InvFact[2 * N] = Pow(Fact[2 * N], MOD - 2);
    for (valueType i = 2 * N - 1; i >= 0; --i)
        InvFact[i] = mul(InvFact[i + 1], i + 1);

    auto C = [&](valueType const &n, valueType const &m) -> valueType {
        if (n < m || m < 0)
            return 0;

        return mul(Fact[n], mul(InvFact[m], InvFact[n - m]));
    };

    valueType Ans = 0;

    for (valueType i = 0; i + 1 < N; ++i) {
        ++Prefix[S[i] - '0'];

        valueType const ch = S[i] - '0';

        if (ch < 9 && Prefix[ch] != 0 && Suffix[ch + 1] != 0) {
            valueType const n = Prefix[ch];
            valueType const m = Suffix[ch + 1];

            Inc(Ans, C(n + m - 1, n));
        }

        --Suffix[S[i + 1] - '0'];
    }

    std::cout << Ans << std::endl;

    return 0;
}

提出情報

ジャッジ結果