結果

問題 No.3178 free sort
ユーザー InTheBloom
提出日時 2025-06-13 22:38:06
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 4,148 bytes
コンパイル時間 4,029 ms
コンパイル使用メモリ 202,236 KB
実行使用メモリ 11,096 KB
最終ジャッジ日時 2025-06-13 22:38:15
合計ジャッジ時間 6,146 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    auto S = readln.chomp.map!(a => a - '0').array;
    const int N = S.length.to!int;
    const long MOD = 998244353;
    alias m = PrimeModuloFactorial!MOD;
    m.build(N + 100);

    auto count = new int[](10);
    foreach (c; S) {
        count[c]++;
    }

    long ans = 0;
    foreach (i; 1 .. 10) {
        if (count[i] == 0) {
            continue;
        }

        count[i]--;
        long add = m.factorial(N - 1);
        foreach (j; 0 .. 10) {
            add *= m.factorial_inv(count[j]);
            add %= MOD;
        }
        count[i]++;

        ans += add;
        ans %= MOD;
    }

    writeln(ans);
}

// check mod_pow
static assert(__traits(compiles, mod_pow(2, 10, 998244353)));

long mod_inv (const long x, const long MOD)
in {
    import std.format : format;
    assert(1 <= MOD, format("MOD must satisfy 1 <= MOD. Now MOD =  %s.", MOD));
    assert(MOD <= int.max, format("MOD must satisfy MOD*MOD <= long.max. Now MOD = %s.", MOD));
}
do {
    return mod_pow(x, MOD-2, MOD);
}

long mod_pow (long a, long x, const long MOD)
in {
    assert(0 <= x, "x must satisfy 0 <= x");
    assert(1 <= MOD, "MOD must satisfy 1 <= MOD");
    assert(MOD <= int.max, "MOD must satisfy MOD*MOD <= long.max");
}
do {
    // normalize
    a %= MOD; a += MOD; a %= MOD;

    long res = 1L;
    long base = a;
    while (0 < x) {
        if (0 < (x&1)) (res *= base) %= MOD;
        (base *= base) %= MOD;
        x >>= 1;
    }

    return res % MOD;
}

// check mod_inv
static assert(__traits(compiles, mod_inv(998244353, 1_000_000_007)));

class PrimeModuloFactorial (ulong M)
{
    /// methods:
    /// - void build (ulong N_)
    /// - long binom (ulong n_, ulong k_)
    /// - long factorial (ulong x_)
    /// - long factorial_inv (ulong x_)

    import std.conv : to;
    import std.format : format;

    // varidate
    static assert(1 <= M && M < int.max, format("PrimeModuloFactorial: M = %s is out of range. M must be in range of [1, %s].", M, int.max));

    private static bool internal_is_prime (int x) {
        if (x <= 1) return false;
        foreach (i; 2..x + 1) {
            if (x < 1L * i * i) break;
            if (x % i == 0) return false;
        }
        return true;
    }
    static assert(internal_is_prime(M.to!int), format("PrimeModuloFactorial: M = %s is not prime number.", M));

    private:
        static long[] fact, fact_inv;
        static int N = 0;
        static long MOD = M;

    public:
        @disable this () {}

        static void build (ulong N_)
        in {
            assert(0 <= N_ && N_ <= 10^^8, format("N = %s does not satisfy constraints. N must be in range of [0, 10^8].", N_));
        }
        do {
            if (N_ <= N) { N = N_.to!int; return; }
            N = N_.to!int;
            fact.length = fact_inv.length = N + 1;

            fact[0] = 1;
            for (int i = 1; i <= N; i++) fact[i] = i * fact[i - 1] % MOD;
            fact_inv[N] = mod_inv(fact[N], MOD);
            for (int i = N; 0 < i; i--) fact_inv[i - 1] = i * fact_inv[i] % MOD;
        }

        static long binom (ulong n_, ulong k_)
        in {
            assert((n_ < k_
                    || (n_ <= N && k_ <= N)),
                    format("Out of range of pre-calculation. MAX = %s, n = %s, k = %s.", N, n_, k_),
                    );
        }
        do {
            int n = n_.to!int;
            int k = k_.to!int;

            if (n < k) return 0;
            long res = fact[n] * fact_inv[k] % MOD;
            return res * fact_inv[n - k] % MOD;
        }

        static long factorial (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_),
                    );
        }
        do {
            int x = x_.to!int;
            return fact[x];
        }

        static long factorial_inv (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_)
                    );
        }
        do {
            int x = x_.to!int;
            return fact_inv[x];
        }
}
0