考え方
こうやって遷移できるんですね．なるほどぉ〜．長さ$j$の文字列を作るとき，新しい文字を$k$個使うとすると，
- 新しい文字（$i+1$番目の文字）を入れる場所を，$j$個の候補から$k$個選べば，
- あとは，$i$種類の文字で長さ$j-k$の文字列をつくる方法の数になる
アライグマ「
— 競技プログラミングをするフレンズ (@kyopro_friends) January 8, 2022
dp[i][j]=i種類目の文字まで使って作れる長さjの文字列の種類数
とすれば、新しい文字をk文字使うとすると
dp[i+1][j]=Σbinom(j,k)*dp[i][j-k]
になるのだ！」
回答例
二項係数を予め（効率的に）計算しておかないとTLEします．from collections import defaultdict S = input() N = len(S) mod = 998244353 fact = [1] * (N + 1) for i in range(N): fact[i + 1] = (i + 1) * fact[i] fact[i + 1] %= mod fact_inv = [1] * (N + 1) fact_inv[N] = pow(fact[N], mod - 2, mod) for i in range(N - 1, -1, -1): fact_inv[i] = (i + 1) * fact_inv[i + 1] fact_inv[i] %= mod ncr = [[1] * (N + 1) for _ in range(N + 1)] for i in range(N + 1): for j in range(i + 1): ncr[i][j] = fact[i] * fact_inv[j] ncr[i][j] %= mod ncr[i][j] *= fact_inv[i - j] ncr[i][j] %= mod cnt = defaultdict(int) for s in S: cnt[s] += 1 dp = [[0] * (N + 1) for _ in range(26 + 1)] dp[0][0] = 1 for i in range(26): for j in range(N + 1): for k in range(min(j, cnt[chr(ord('a') + i)]) + 1): dp[i + 1][j] += ncr[j][k] * dp[i][j - k] dp[i + 1][j] %= mod ans = -1 for i in range(N + 1): ans += dp[26][i] ans %= mod print(ans)
