結果
問題 | No.1646 Avoid Palindrome |
ユーザー | taiga0629kyopro |
提出日時 | 2021-08-29 02:16:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,160 ms / 3,000 ms |
コード長 | 1,202 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 431,004 KB |
最終ジャッジ日時 | 2024-11-22 01:41:14 |
合計ジャッジ時間 | 56,820 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
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)