結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー 伟国姚
提出日時 2025-05-08 18:55:06
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,720 bytes
コンパイル時間 3,950 ms
コンパイル使用メモリ 80,548 KB
実行使用メモリ 52,016 KB
最終ジャッジ日時 2025-05-08 18:55:17
合計ジャッジ時間 9,494 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 的方案数
        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++) {
            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;
                        }
                    }
                }


            } 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());
        }
    }
}
0