ABC242-E (∀x∀)

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("3");
            WillReturn.Add("AXA");
            WillReturn.Add("6");
            WillReturn.Add("ABCZAZ");
            WillReturn.Add("30");
            WillReturn.Add("QWERTYUIOPASDFGHJKLZXCVBNMQWER");
            WillReturn.Add("28");
            WillReturn.Add("JVIISNEOXHSNEAAENSHXOENSIIVJ");
            WillReturn.Add("31");
            WillReturn.Add("KVOHEEMSOZZASHENDIGOJRTJVMVSDWW");
            //24
            //29
            //212370247
            //36523399
            //231364016
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static Dictionary<long, long> mBekiDict = new Dictionary<long, long>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        // 26のべき乗を求めておく
        long BekiVal = 1;
        for (long I = 1; I <= 1000000; I++) {
            BekiVal *= 26;
            BekiVal %= Hou;
            mBekiDict[I] = BekiVal;
        }

        var sb = new System.Text.StringBuilder();
        for (long I = 2; I <= InputList.Count - 1; I += 2) {
            long Result = Solve(InputList[(int)I]);
            sb.Append(Result);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    static long Solve(string pS)
    {
        long UB = pS.Length - 1;
        long UB_Half = UB / 2;

        long Answer = 0;

        // 文字自由になる位置を全探索
        for (long I = 0; I <= UB_Half; I++) {
            long LowerCnt = pS[(int)I] - 'A';
            long RestRange = UB_Half - I;

            long CurrPatternCnt = LowerCnt;
            if (RestRange > 0) {
                CurrPatternCnt *= mBekiDict[RestRange];
            }

            Answer += CurrPatternCnt;
            Answer %= Hou;
        }

        // 文字自由にならない場合の1通りがあるかを調べる
        var sb = new System.Text.StringBuilder();
        for (long I = 0; I <= pS.Length - 1; I++) {
            if (UB_Half < I) {
                long RevInd = UB - I;
                sb.Append(pS[(int)RevInd]);
            }
            else {
                sb.Append(pS[(int)I]);
            }
        }
        string RevStr = sb.ToString();

        if (RevStr.CompareTo(pS) <= 0) {
            Answer++;
            Answer %= Hou;
        }

        return Answer;
    }
}

解説

桁DPの感覚で
文字が自由になる位置を全探索してます。