結果

問題 No.1195 数え上げを愛したい（文字列編）
コンテスト
ユーザー Forested
提出日時 2020-08-24 16:36:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,917 ms / 3,000 ms
コード長 4,588 bytes
コンパイル時間 9,108 ms
コンパイル使用メモリ 266,436 KB
最終ジャッジ日時 2025-01-13 13:27:28
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003;
template <typename T> inline bool chmin(T& x, const T& y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T& x, const T& y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Number-Theoretical Transform
// for example, (998244353, 31), (1012924417, 198), (1811939329, 136)
template <int mod, int base>
struct NumberTheoreticalTransform {
    vector<ll> zeta, inv_zeta;
    NumberTheoreticalTransform() {
        size_t exponents = 0;
        int tmp = mod - 1;
        while (not (tmp & 1)) {
            tmp >>= 1;
            ++exponents;
        }
        zeta.resize(exponents + 1);
        inv_zeta.resize(exponents + 1);
        zeta[exponents] = base;
        inv_zeta[exponents] = mod_pow(base, mod - 2);
        for (size_t i = exponents; i > 0; --i) {
            zeta[i - 1] = zeta[i] * zeta[i] % mod;
            inv_zeta[i - 1] = inv_zeta[i] * inv_zeta[i] % mod;
        }
    }
    ll mod_pow(ll x, ll y) {
        if (not y) return 1;
        ll a = mod_pow(x, y >> 1);
        if (y & 1) return a * a % mod * x % mod;
        return a * a % mod;
    }
    inline ll add(ll x, ll y) {
        if ((x += y) >= mod) x -= mod;
        return x;
    }
    void dft(vector<ll> &a, size_t exponents) {
        size_t m = 1 << exponents, now_e = exponents;
        while (m > 1) {
            for (size_t i = 0; i < a.size() / m; ++i) {
                ll now = 1;
                for (size_t j = 0; j < m / 2; ++j) {
                    ll l = a[m * i + j];
                    ll r = a[m * i + j + m / 2];
                    a[m * i + j] = add(l, r);
                    a[m * i + j + m / 2] = add(l, mod - r) * now % mod;
                    now = now * zeta[now_e] % mod;
                }
            }
            m >>= 1;
            --now_e;
        }
    }
    void idft(vector<ll> &a, size_t exponents) {
        size_t m = 2, now_e = 1;
        while (m <= a.size()) {
            for (size_t i = 0; i < a.size() / m; ++i) {
                ll now = 1;
                for (size_t j = 0; j < m / 2; ++j) {
                    ll l = a[m * i + j];
                    ll r = a[m * i + j + m / 2] * now % mod;
                    a[m * i + j] = add(l, r);
                    a[m * i + j + m / 2] = add(l, mod - r);
                    now = now * inv_zeta[now_e] % mod;
                }
            }
            m <<= 1;
            ++now_e;
        }
    }
    vector<ll> multiply(vector<ll> f, vector<ll> g) {
        size_t siz = 1, exp = 0;
        while (siz < f.size() + g.size()) {
            siz *= 2;
            ++exp;
        }
        vector<ll> nf(siz, 0), ng(siz, 0);
        for (size_t i = 0; i < f.size(); ++i) nf[i] = f[i];
        for (size_t i = 0; i < g.size(); ++i) ng[i] = g[i];
        dft(nf, exp);
        dft(ng, exp);
        for (size_t i = 0; i < siz; ++i) nf[i] = nf[i] * ng[i] % mod;
        idft(nf, exp);
        ll inv = mod_pow(siz, mod - 2);
        for (size_t i = 0; i < siz; ++i) nf[i] = nf[i] * inv % mod;
        return nf;
    }
};

// Main
constexpr int MOD = 998244353, ROOT = 31;

int main() {
    NumberTheoreticalTransform<MOD, ROOT> ntt;
    
    string s;
    cin >> s;
    
    vector<int> cnt(26, 0);
    for (char c: s) ++cnt[c - 'a'];
    // sort(all(cnt));
    
    vector<ll> fact(s.size() + 1), inv_fact(s.size() + 1);
    fact[0] = 1;
    rep(i, s.size()) fact[i + 1] = fact[i] * (i + 1) % MOD;
    inv_fact[s.size()] = ntt.mod_pow(fact[s.size()], MOD - 2);
    per(i, s.size()) inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    
    vector<ll> dp(s.size() + 1, 0);
    dp[0] = 1;
    rep(i, 26) {
        vector<ll> f(s.size() + 1), g(cnt[i] + 1);
        rep(j, s.size() + 1) f[j] = dp[j] * inv_fact[j] % MOD;
        rep(j, cnt[i] + 1) g[j] = inv_fact[j] % MOD;
        vector<ll> m = ntt.multiply(f, g);
        rep(i, s.size() + 1) dp[i] = m[i] * fact[i] % MOD;
    }
    
    ll ans = 0;
    rep(i, 1, s.size() + 1) ans += dp[i];
    ans %= MOD;
    cout << ans << "\n";
    return 0;
}
0