AGC019B
https://gyazo.com/0f9d4abc0da3abe12d279a7e8d78c384
考えたこと
長さの偶奇で分けて考えるべきかな？
中心を固定して広げていくと、新しく範囲に入る文字が異なってれば2倍、異なってなければ1倍かな
それでも全然効率よくないね
20万文字あるのに「余りを答えよ」ではないのが不思議
範囲を定義域にするDPか？
ある2ペアの文字が異なってる場合、そのペアの交換を含む範囲は全部場合の数を+1する
はっ、包除原理か？
いや、対称性で絞れないから違うか
公式解説
異なる2種の文字を両端として作られる文字列は、互いに一致することがない
https://gyazo.com/a6db0731133b26e95552e75a13baa401
これに気づけば余事象を引くで「一致するペアの数を数える」に変わる 問題分割