結果
問題 | No.2131 Concon Substrings (COuNt Version) |
ユーザー | Navier_Boltzmann |
提出日時 | 2023-11-25 14:44:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 802 ms / 2,000 ms |
コード長 | 1,663 bytes |
コンパイル時間 | 731 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 147,048 KB |
最終ジャッジ日時 | 2023-11-25 14:44:11 |
合計ジャッジ時間 | 7,520 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
55,604 KB |
testcase_01 | AC | 44 ms
55,604 KB |
testcase_02 | AC | 44 ms
55,604 KB |
testcase_03 | AC | 358 ms
108,520 KB |
testcase_04 | AC | 45 ms
55,604 KB |
testcase_05 | AC | 45 ms
55,604 KB |
testcase_06 | AC | 45 ms
55,604 KB |
testcase_07 | AC | 801 ms
147,048 KB |
testcase_08 | AC | 212 ms
94,056 KB |
testcase_09 | AC | 802 ms
146,920 KB |
testcase_10 | AC | 742 ms
146,664 KB |
testcase_11 | AC | 529 ms
125,416 KB |
testcase_12 | AC | 492 ms
122,984 KB |
testcase_13 | AC | 57 ms
66,416 KB |
testcase_14 | AC | 237 ms
97,256 KB |
testcase_15 | AC | 203 ms
93,032 KB |
testcase_16 | AC | 60 ms
68,520 KB |
testcase_17 | AC | 193 ms
91,240 KB |
testcase_18 | AC | 189 ms
91,368 KB |
testcase_19 | AC | 135 ms
83,932 KB |
ソースコード
from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.readline N = int(input()) mod = 998244353 # class combination(): # def __init__(self,N,p): # self.fact = [1, 1] # fact[n] = (n! mod p) # self.factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p) # self.inv = [0, 1] # factinv 計算用 # self.p = p # for i in range(2, N + 1): # self.fact.append((self.fact[-1] * i) % p) # self.inv.append((-self.inv[p % i] * (p // i)) % p) # self.factinv.append((self.factinv[-1] * self.inv[-1]) % p) # def cmb(self,n, r): # if (r < 0) or (n < r): # return 0 # r = min(r, n - r) # return self.fact[n] * self.factinv[r] * self.factinv[n-r] % self.p # C = combination(10000) M = N//3 + 1 dp = [[[0]*N for j in range(M+1)] for _ in range(3)] dp[0][0][0] = 1 for i in range(N-1): for j in range(M): for k in range(3): #dp[k][j][i] if k==2: dp[0][j+1][i+1] = (dp[0][j+1][i+1] + dp[k][j][i])%mod else: dp[k+1][j][i+1] = (dp[k+1][j][i+1] + dp[k][j][i])%mod dp[k][j][i+1] = (dp[k][j][i+1] + 25*dp[k][j][i])%mod if (k==0)&(j==0): dp[k][j][i+1] = (dp[k][j][i+1] + pow(25,i+1,mod))%mod ans = 0 for j in range(M+1): ans += dp[2][j][-1]*(j+1) ans += dp[1][j][-1]*(j) ans += dp[0][j][-1]*(j) ans %= mod # print(dp[2]) # print(dp) print(ans)