けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

数え上げ問題を期待値に帰着する

AOJ 2959 Revenge of UMG (HUPC 2019 day2-H)

この問題のテスターをやってた! 今流行の NTT 系問題!!しかも分割統治 + FFT というカッコいいやつ!! 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…