結果

問題 No.3178 free sort
コンテスト
ユーザー pessimist
提出日時 2025-06-13 22:14:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 1,099 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 197,944 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-13 22:14:47
合計ジャッジ時間 4,557 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAX = 200005;

ll fact[MAX], inv_fact[MAX];
ll modpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void prepare_factorials() {
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i < MAX; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        inv_fact[i] = modpow(fact[i], MOD - 2);
    }
}
ll multinomial(const vector<int>& freq, int total_digits) {
    ll res = fact[total_digits];
    for (int f : freq) {
        res = res * inv_fact[f] % MOD;
    }
    return res;
}

int main() {
    string N;
    cin >> N;

    prepare_factorials();

    vector<int> freq(10, 0);
    for (char c : N) freq[c - '0']++;

    int total_digits = N.size();

    ll total = multinomial(freq, total_digits);

    if (freq[0] > 0) {
        freq[0]--; 
        ll bad = multinomial(freq, total_digits - 1);
        total = (total - bad + MOD) % MOD;
    }

    cout << total << endl;
    return 0;
}
0