阿祁的部落格

AtCoder ABC 242 pE.  解題心得( 題目 )

解題概念:greedy

解題方法:從中間向兩側檢查，掃描右邊是否比左邊小或大(越中間的越優先)，如果是左邊比較大，那就沒限制，因為是回文，只要前半段符合條件後半段也符合。

如果不符合，就是不能拿到最極限，像字串BAA就是一種例子，在下方程式碼的base case就有因此調整。

Java參考程式碼(更好意見可留言於下方，謝謝!):

//Author:En Chi Tsung(欉恩祁)

//Date:2022/03/06

import java.util.*;

import java.io.*;

public class Main {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int ret,rd,N;

    public static final int p=998244353;

    public static long[] pow=new long[1000005];

    public static long[] DP=new long[1000005];

    public static String in;

    public static boolean ok=false;

    public static void main(String[] args) throws Exception{

        in=br.readLine();

        final int t=Integer.parseInt(in);

        pow[0]=1;

        for(int i=1;i<1000005;i++) {

            pow[i]=pow[i-1]*26%p;

        }

        for(int q=0;q<t;q++) {

            in=br.readLine();

            final int n=Integer.parseInt(in);

            in=br.readLine();

            if(n==1) { //Special judge

                bw.write((in.charAt(0)-'A'+1)+"\n");

                continue;

            }

            ok=true;

            N=(n-1)/2;

            for(int i=n/2-1;i>=0;i--) {

                if(in.charAt(i)<in.charAt(n-i-1)) {

                    ok=true;

                    break;

                }

                if(in.charAt(i)>in.charAt(n-i-1)) {

                    ok=false;

                    break;

                }

            }

            if(ok) {

                DP[N+1]=1;

            }

            else {

                DP[N+1]=0;

            }

            for(int i=N;i>=0;i--) {

                DP[i]=(DP[i+1]+(in.charAt(i)-'A')*pow[N-i])%p;

            }

            bw.write(DP[0]+"\n");

        }

        bw.flush();

    }

}