結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2025-05-08 18:59:53 |
言語 | Java (openjdk 23) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,149 bytes |
コンパイル時間 | 2,717 ms |
コンパイル使用メモリ | 80,348 KB |
実行使用メモリ | 214,564 KB |
最終ジャッジ日時 | 2025-05-08 19:00:31 |
合計ジャッジ時間 | 35,214 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 RE * 2 |
ソースコード
import java.io.*; import java.util.StringTokenizer; /** * Date: 2025/5/8 17:41 */ public class Main { public static void main(String[] args) { int n = sc.nextInt(); char[] s = sc.next().toCharArray(); for (int i = 1; i < n; i++) { if (s[i] == s[i - 1] && s[i] != '?') { out.println(0); out.close(); return; } } for (int i = 2; i < n; i++) { if (s[i] == s[i - 2] && s[i] != '?') { out.println(0); out.close(); return; } } int mod = 998244353; int m = 26; int[][][] dp = new int[n][m][m];//dp[i][j][k] = s[i] = j , s[i-1] = k 的方案数 int[][] ps = new int[m][m + 1]; if (s[0] == '?') { if (s[1] == '?') { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { if (i == j) continue; dp[1][i][j] = 1; } } } else { int idx = s[1] - 'a'; for (int i = 0; i < m; i++) { if (i == idx) continue; dp[1][idx][i] = 1; } } } else { if (s[1] == '?') { int idx = s[0] - 'a'; for (int i = 0; i < m; i++) { if (i == idx) continue; dp[1][i][idx] = 1; } } else { int i1 = s[0] - 'a', i2 = s[1] - 'a'; dp[1][i2][i1] = 1; } } for (int i = 2; i < n; i++) { for (int z = 0; z < m; z++) { for (int j = 0; j < m; j++) { ps[z][j + 1] = ps[z][j] + dp[i - 1][z][j]; ps[z][j + 1] %= mod; } } if (s[i] == '?') { for (int j = 0; j < m; j++) { for (int k = 0; k < m; k++) { if (k == j) continue; /* for (int l = 0; l < m; l++) { if (l == j || l == k) continue; dp[i][j][k] += dp[i - 1][k][l]; dp[i][j][k] %= mod; }*/ dp[i][j][k] += ps[k][m] - dp[i - 1][k][j] - dp[i - 1][k][k]; dp[i][j][k] = ((dp[i][j][k] % mod) + mod) % mod; } } } else { int idx = s[i] - 'a'; for (int j = 0; j < m; j++) { if (j == idx) continue; for (int k = 0; k < m; k++) { if (k == idx || k == j) continue; dp[i][idx][j] = (dp[i][idx][j] + dp[i - 1][j][k]) % mod; } } } } int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { ans += dp[n - 1][i][j]; ans %= mod; } } out.println(ans); out.close(); } static Kattio sc = new Kattio(); static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static class Kattio { static BufferedReader r; static StringTokenizer st; public Kattio() { r = new BufferedReader(new InputStreamReader(System.in)); } public String next() { try { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(r.readLine()); } return st.nextToken(); } catch (Exception e) { return null; } } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } } }