B - Reverse and Compare 考えたこと 長さの偶奇で分けて考えるべきかな? 中心を固定して広げていくと、新しく範囲に入る文字が異なってれば2倍、異なってなければ1倍かな それでも全然効率よくないね 20万文字あるのに「余りを答えよ」ではないのが不思議 範囲を定義域にするDPか? ある2ペアの文字が異なってる場合、そのペアの交換を含む範囲は全部場合の数を+1する はっ、包除原理か? いや、対称性で絞れないから違うか 公式解説 異なる2種の文字を両端として作られる文字列は、互いに一致することがない 操作の結果が同一になる条件 Xであるものの数え上げ→Xならば? これに気づけば余事象を引くで「一致するペアの数を数える」に変わる これは頻度→三角数で求まる 問題分割 列の範囲更新 操作の結果の数え上げ