結果
| 問題 | No.1195 数え上げを愛したい（文字列編） |
| ユーザー |
 strangerxxx
|
| 提出日時 | 2022-05-13 11:26:59 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,718 bytes |
| コンパイル時間 | 95 ms |
| コンパイル使用メモリ | 12,800 KB |
| 実行使用メモリ | 120,432 KB |
| 最終ジャッジ日時 | 2024-07-21 08:48:52 |
| 合計ジャッジ時間 | 8,937 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
def resolve():
MOD = 998244353
s = input()
n = len(s)
d = [0] * 27
for i in s:
d[ord(i) - ord("a") + 1] += 1
cmb = Combination(n + 1)
dp = [[0] * (n + 1) for _ in range(27)]
dp[0][0] = 1
for i in range(1, 27):
for j in range(n + 1):
for k in range(min(j, d[i]) + 1):
dp[i][j] += dp[i - 1][j - k] * cmb(j, k)
dp[i][j] %= MOD
print(sum(dp[-1][1:]) % MOD)
class Combination:
"""
前計算modあり組み合わせ
"""
def __init__(self, n_max, mod=998244353):
self.n_max = n_max
self.mod = mod
self.modinv = self.make_modinv_list(n_max)
self.fac, self.facinv = self.make_factorial_list(n_max)
def __call__(self, n, r):
if r < 0 or n < r:
return 0
if r > self.n_max:
raise ValueError("n is larger than n_max.")
return self.fac[n] * self.facinv[r] % self.mod * \
self.facinv[n - r] % self.mod
def make_modinv_list(self, n):
# 0からnまでのmod逆元のリスト
modinv = [0] * (n + 1)
modinv[1] = 1
for i in range(2, n + 1):
modinv[i] = self.mod - self.mod // i * \
modinv[self.mod % i] % self.mod
return modinv
def make_factorial_list(self, n):
# 階乗のリストと階乗のmod逆元のリスト
fac = [None] * (n + 1)
fac[0] = 1
facinv = [None] * (n + 1)
facinv[0] = 1
for i in range(1, n + 1):
fac[i] = fac[i - 1] * i % self.mod
facinv[i] = facinv[i - 1] * self.modinv[i] % self.mod
return fac, facinv
if __name__ == '__main__':
resolve()