\(S\) の空でない、連続した部分列 \(S'\) を並び替えて得られる文字列の種類数は、\(S'\) における各アルファベットの出現数のみに依存します。

そのためこの問題を動的計画法に落とし込む際には

• 何番目のアルファベットまでを使ったか
• 合計で何文字を使ったか

の \(2\) つを状態に持つことが重要であり、故に以下のような動的計画法を考えることが有効です。

• \(\text{dp}_{i,j}:=(\)アルファベットの昇順で \(i\) 番目のアルファベットまでを使い、使った文字数の合計が \(j\) であるような \(S\) の部分列、およびその並び替えの個数\()\)

そしてその遷移は、\(S\) における a から z までのアルファベットの出現数をそれぞれ \(\text{freq}_1,\text{freq}_2,\ldots,\text{freq}_{26}\) として以下のようになります。

• \(\text{dp}_{i,j} = \sum_{k=0}^{\min(j,\text{freq}_i)} \text{dp}_{i-1,j-k} \times \binom{j}{k}\)

計算量は一見すると \(σ=26\), \(N\) を \(S\) の長さとして \(O(σN^2)\) かかっていそうですが、\(\text{dp}_{i,j}\) への遷移にかかる計算量が高々 \(O(\text{freq}_i)\) であることを踏まえると合計での計算量は高々 \(O(\sum_{i=1}^{26} \text{freq}_i \times N)=O((\sum_{i=1}^{26} \text{freq}_i) \times N)=O(N \times N)=O(N^2)\) となります。

求める答えは \(\sum_{i=1}^{N} \text{dp}_{26,i}\) です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const ll MAX = 5010, MOD = 998244353;

vector<ll> fac,finv,inv;

void binom_init() {
    fac.resize(MAX);
    finv.resize(MAX);
    inv.resize(MAX);
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    finv[0] = finv[1] = 1;
    for(int i=2; i<MAX; i++){
        fac[i] = fac[i-1]*i%MOD;
        inv[i] = MOD-MOD/i*inv[MOD%i]%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

ll binom(ll n, ll r){
    if(n<r || n<0 || r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}

int main(){
    binom_init();
    string S; cin >> S;
    int N = S.size();
    vector<int> freq(26);
    for(auto el: S) freq[el-'a']++;
    vector<vector<ll>> dp(27,vector<ll>(N+1));
    dp[0][0] = 1;
    for(int i=0; i<26; i++){
        for(int j=0; j<=N; j++){
            for(int k=0; k<=min(j,freq[i]); k++){
                dp[i+1][j] += dp[i][j-k]*binom(j,k);
                dp[i+1][j] %= MOD;
            }
        }
    }
    ll ans = 0;
    for(int i=1; i<=N; i++){
        ans += dp[26][i];
        ans %= MOD;
    }
    cout << ans << endl;
}