オンライン処理を実現する分割統治法
AtCoder
ABC-Ex
橙色diff
多項式・FPS(形式的冪級数)
DP
順列を題材とした問題
順列の数え上げ
順列テク:巡回群の直積と見る
FFT
DP高速化
DP高速化:FFT
分割統治FFT
分割統治法
二項係数
包除原理:対称性
包除原理
数え上げ問題
解空間:O(N!)通りの選択肢
指数型FPS
メタアルゴリズム問題
なもりグラフ
入力が定数個
数珠
AtCoder650点
オンライン処理を実現する分割統治法
コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…
AtCoder
AtCoder600点
ABC-Ex
赤色diff
高速畳み込み計算
分割統治法
オンライン処理を実現する分割統治法
DP
多項式・FPS(形式的冪級数)
分割統治FFT
FFT
DP高速化
DP高速化:FFT
平方分割
漸化式
数え上げ問題
フラクタル構造
入力が定数個
この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…
AtCoder
AtCoder600点
ABC-Ex
赤色diff
FFT
分割統治法
分割統治FFT
DP高速化:FFT
DP高速化
グラフ
数え上げ問題
制約条件:総和=K
オンライン処理を実現する分割統治法
オンライン分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 …
AOJ
HUPC
FFT
ワイルドカード問題
分割統治法
制約条件:等間隔
総和を求める
文字列
3つのものの真ん中に着目
多項式・FPS(形式的冪級数)
主客転倒
f(i,j)をiとjとに分離する
個別の要素の動きに注目する
数え上げ問題
数え上げ問題を期待値に帰着する
高速畳み込み計算
オンライン処理を実現する分割統治法
3つ組(i<j<k)の問題
0と1と2の問題
高度典型
中堅以上の典型要素を詰め合わせた教育的問題
この問題のテスターをやってた! 今流行の NTT 系問題!!しかも分割統治 + FFT というカッコいいやつ!! 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…