分割統治FFT
分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 ... 長さ …
AOJ
HUPC
FFT
ワイルドカード問題
分割統治法
制約条件:等間隔
総和を求める
文字列問題
3つのものの真ん中に着目
多項式・形式的冪級数
縦に見るものを横に見る
f(i,j)をiとjとに分離する
個別の要素の動きに注目する
数え上げ問題
数え上げ問題を期待値に帰着する
高速畳み込み計算
分割統治FFT
この問題のテスターをやってた! 今流行の NTT 系問題!!しかも分割統治 + FFT というカッコいいやつ!! 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…