結果
問題 | No.1646 Avoid Palindrome |
ユーザー | taiga0629kyopro |
提出日時 | 2021-08-29 02:12:58 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,135 bytes |
コンパイル時間 | 1,396 ms |
コンパイル使用メモリ | 81,892 KB |
実行使用メモリ | 431,268 KB |
最終ジャッジ日時 | 2024-05-01 19:28:38 |
合計ジャッジ時間 | 73,982 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 60 ms
64,768 KB |
testcase_01 | AC | 64 ms
66,176 KB |
testcase_02 | AC | 58 ms
64,512 KB |
testcase_03 | AC | 64 ms
66,688 KB |
testcase_04 | AC | 2,414 ms
410,344 KB |
testcase_05 | AC | 2,167 ms
410,104 KB |
testcase_06 | AC | 2,247 ms
399,308 KB |
testcase_07 | AC | 2,366 ms
410,580 KB |
testcase_08 | AC | 2,388 ms
413,236 KB |
testcase_09 | AC | 2,268 ms
397,068 KB |
testcase_10 | AC | 2,273 ms
404,588 KB |
testcase_11 | AC | 2,216 ms
395,988 KB |
testcase_12 | AC | 2,181 ms
409,880 KB |
testcase_13 | AC | 2,172 ms
413,796 KB |
testcase_14 | AC | 2,033 ms
403,344 KB |
testcase_15 | AC | 1,882 ms
409,752 KB |
testcase_16 | AC | 1,695 ms
401,436 KB |
testcase_17 | AC | 2,062 ms
415,868 KB |
testcase_18 | AC | 2,046 ms
406,900 KB |
testcase_19 | AC | 2,122 ms
405,244 KB |
testcase_20 | AC | 1,778 ms
407,544 KB |
testcase_21 | AC | 1,840 ms
415,484 KB |
testcase_22 | AC | 2,032 ms
403,968 KB |
testcase_23 | AC | 1,774 ms
417,860 KB |
testcase_24 | AC | 2,196 ms
430,084 KB |
testcase_25 | AC | 2,178 ms
430,528 KB |
testcase_26 | AC | 2,220 ms
430,276 KB |
testcase_27 | AC | 2,139 ms
430,284 KB |
testcase_28 | AC | 2,144 ms
430,356 KB |
testcase_29 | AC | 2,473 ms
430,796 KB |
testcase_30 | AC | 2,363 ms
431,052 KB |
testcase_31 | AC | 2,432 ms
430,924 KB |
testcase_32 | AC | 2,368 ms
431,268 KB |
testcase_33 | AC | 2,622 ms
430,868 KB |
testcase_34 | AC | 2,084 ms
430,356 KB |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | AC | 47 ms
57,984 KB |
testcase_38 | AC | 44 ms
53,248 KB |
testcase_39 | AC | 43 ms
52,864 KB |
testcase_40 | AC | 43 ms
52,992 KB |
testcase_41 | AC | 55 ms
61,056 KB |
testcase_42 | AC | 53 ms
61,056 KB |
testcase_43 | AC | 2,658 ms
430,536 KB |
ソースコード
mod=998244353 n=int(input()) s=list(input())+["#"] for i in range(n): s[i]=ord(s[i])-97 def _(i,j,k): return (j*27+k)*(n+2)+i dp=[0]*(n+3)*900 if s[0]==s[1]==-34: for i in range(26): for j in range(26): if i!=j:dp[_(1,i,j)]+=1 elif s[0]==-34: for i in range(26): if i!=s[1]:dp[_(1,i,s[1])]+=1 elif s[1]==-34: for i in range(26): if i!=s[0]:dp[_(1,s[0],i)]+=1 else: if s[0]!=s[1]:dp[_(1,s[0],s[1])]+=1 sdp=[0]*30 for i in range(1,n): for j in range(26): for k in range(26): if j==k:continue if i>=2 and s[i]==-34: dp[_(i,j,k)]+=sdp[j]-dp[_(i-1,k,j)] dp[_(i,j,k)]%=mod if i==n-1:continue if s[i+1]!=-34: if s[i+1]==j or s[i+1]==k:continue dp[_(i+1,k,s[i+1])]+=dp[_(i,j,k)] dp[_(i + 1, k, s[i + 1])]%=mod else: pass for j in range(26): sdp[j]=sum(dp[_(i,k,j)] for k in range(26))%mod ans=0 for i in range(26): for j in range(26): ans+=dp[_(n-1,i,j)] ans%=mod print(ans)