結果
問題 | No.1646 Avoid Palindrome |
ユーザー | taiga0629kyopro |
提出日時 | 2021-08-29 02:16:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,340 ms / 3,000 ms |
コード長 | 1,202 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,620 KB |
実行使用メモリ | 430,940 KB |
最終ジャッジ日時 | 2024-05-01 19:31:05 |
合計ジャッジ時間 | 59,377 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
64,640 KB |
testcase_01 | AC | 56 ms
65,920 KB |
testcase_02 | AC | 52 ms
64,512 KB |
testcase_03 | AC | 56 ms
67,072 KB |
testcase_04 | AC | 1,976 ms
410,512 KB |
testcase_05 | AC | 1,768 ms
410,524 KB |
testcase_06 | AC | 1,879 ms
398,720 KB |
testcase_07 | AC | 1,950 ms
410,000 KB |
testcase_08 | AC | 2,009 ms
413,356 KB |
testcase_09 | AC | 1,857 ms
397,572 KB |
testcase_10 | AC | 1,936 ms
404,860 KB |
testcase_11 | AC | 1,816 ms
396,000 KB |
testcase_12 | AC | 1,784 ms
409,692 KB |
testcase_13 | AC | 1,773 ms
413,356 KB |
testcase_14 | AC | 1,656 ms
403,488 KB |
testcase_15 | AC | 1,522 ms
410,444 KB |
testcase_16 | AC | 1,380 ms
401,980 KB |
testcase_17 | AC | 1,667 ms
415,640 KB |
testcase_18 | AC | 1,663 ms
406,568 KB |
testcase_19 | AC | 1,655 ms
405,300 KB |
testcase_20 | AC | 1,414 ms
407,688 KB |
testcase_21 | AC | 1,432 ms
415,560 KB |
testcase_22 | AC | 1,638 ms
403,884 KB |
testcase_23 | AC | 1,434 ms
417,788 KB |
testcase_24 | AC | 1,775 ms
430,724 KB |
testcase_25 | AC | 1,772 ms
430,380 KB |
testcase_26 | AC | 1,778 ms
430,380 KB |
testcase_27 | AC | 1,758 ms
430,548 KB |
testcase_28 | AC | 1,757 ms
430,432 KB |
testcase_29 | AC | 2,038 ms
430,852 KB |
testcase_30 | AC | 1,910 ms
430,808 KB |
testcase_31 | AC | 1,937 ms
430,696 KB |
testcase_32 | AC | 1,949 ms
430,796 KB |
testcase_33 | AC | 2,209 ms
430,912 KB |
testcase_34 | AC | 1,730 ms
430,340 KB |
testcase_35 | AC | 38 ms
52,224 KB |
testcase_36 | AC | 39 ms
52,480 KB |
testcase_37 | AC | 40 ms
57,984 KB |
testcase_38 | AC | 38 ms
52,736 KB |
testcase_39 | AC | 38 ms
53,364 KB |
testcase_40 | AC | 38 ms
53,300 KB |
testcase_41 | AC | 45 ms
61,452 KB |
testcase_42 | AC | 46 ms
61,460 KB |
testcase_43 | AC | 2,340 ms
430,940 KB |
ソースコード
mod=998244353 n=int(input()) s=list(input())+["#"] for i in range(n): s[i]=ord(s[i])-97 if n==1: if s[0]==-34:print(26) else:print(1) exit() 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)