結果

問題 No.1755 Almost Palindrome
ユーザー maguroflymagurofly
提出日時 2021-11-20 15:57:50
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 2,860 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-06-11 17:21:58
合計ジャッジ時間 1,209 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

T = gets.to_i
MOD = 998244353
inv = ->n{ n.pow(MOD-2, MOD) }
B = 26
T.times do
    n = gets.to_i
    # print "#{n} -> "
    if n == 1
        puts 0
        next
    end

=begin
長さ l 、半径 r の回文のうち、中心に m 個同じ文字が連続するものを考える
中心に同じ文字が m 個連続するとは、回文の中央から片方の端まで m 個連続しているということ

長さ r の回文であって、中心に m 個同じ文字が連続するものは
- m = n のとき、 26 個ある
    - すべて同じ文字なので、 26 通り
- m < n のとき、 26^(r - m) * 25 個ある
    - r = 5, m = 2 のときは、 XYzAA ただし z は 25 文字（z != A)
    - 26^(r - m - 1) * 25 * 26 = 26^(r - m) * 25

長さ r の回文であって、中心に m 個同じ文字が連続するものに、何か文字を挿入して回文でなくするには？
- 中央と異なる文字
    - l が偶数のとき、中央以外に挿入できるので 25l 通り
    - l が奇数のとき、どこにでも挿入できるので 25(l+1) 通り
- 中央と同じ文字
    - m = r のとき、 何処にも挿入できない  
    - m < r のとき
      - 中央に連続する文字の周辺には挿入できない m 文字連続するとき、
        - l が偶数なら 実際は 2m 文字連続しているので 2m + 1 箇所つぶされる よって (l + 1) - (2m + 1) = l - 2m
        - l が奇数なら 実際は 2m-1 文字連続しているので 2m 箇所つぶされる よって (l + 1) - 2m = l - 2m + 1

よって答えは
- l が偶数のとき、
  - 中央と異なる文字を挿入する 26^r * 25l
  - 中央と同じ文字を挿入する 26^(r - m) * 25 * (l - 2m)
  - 合計で、 26^r * 25l + sum[m=1..r-1] 26^(r-m) * 25 * (l-2m)
  - = 25l * 26^r + l(26^r - 26) - 52/25 * (-25r + 26^r - 1)
  - # p26r = 26.pow(r, MOD)
  - = 25 * l * p26r + l * (p26r - 26) - 52 * inv[25] * (-25 * r + p26r - 1)
- l が奇数のとき
  - 中央と異なる文字を挿入する 26^r * 25(l+1)
  - 中央と同じ文字を挿入する 26^(r - m) * 25 * (l - 2m + 1)
  - 合計で、 26^r * 25(l + 1) + sum[m=1..r-1] 26^(r - m) * 25 * (l - 2m + 1)
  - = l(26^r - 26) + 25(l + 1) * 26^r + 1/25 * (-27 * 26^r - 598) + 52r
  - = l * (p26r - 26) + 25 * (l + 1) * p26r + inv[25] * (-27 * p26r - 598) + 52 * r

=end
    l = n - 1 # 回文の長さ
    r = (l + 1) / 2 # 回文の半径
    p26r = B.pow(r, MOD)
    if l.even?
      ans = (B - 1) * l * p26r + l * (p26r - B) - 2 * B * inv[B - 1] * (-(B - 1) * r + p26r - 1)
      ans %= MOD
      puts ans
    else
      ans = l * (p26r - B) + (B - 1) * (l + 1) * p26r + inv[B - 1] * (-(B + 1) * p26r - B * (B - 3)) + 2 * B * r
    # ans = (B - 1) * l * p26r + l * (p26r - B) - 2 * B * inv[B - 1] * (-(B - 1) * r + p26r - 1)
      ans %= MOD
      puts ans
    end
end
0