数え上げテクニック集

状態を同一視することで高速化する

まとめられる条件

遷移先状態が同じ

遷移につく係数が同じ

まとめられた状態すべてが問題文の条件を満たすか満たさないかのどちらか

DPで順列を決める場合「何を既に使ったか」を管理する必要がある

並び順でやるのではなく、入れるものを昇順/降順でやる

5 greedy からの帰着

「操作で作られる可能性のある列の個数を求めよ」は複数の操作列で同じ列が作られる時に難しい

産物から操作列を一意に定める方法があれば数えやすくなる

6 場合分けのテクニック

パラメータで場合わけ

disjointになるように注意

不変量の数の予想

偶数なら偶奇の不変量がありそう

9 再帰的な定義の利用

11 高速化のテクニック

11.2 データ構造の利用

11.3 配列の使いまわし

結合法則と交換法則を満たす演算に使える

11.7 簡単な枝刈り

12 行列を用いたテクニック 26

コンパニオン行列の累乗

多項式の累乗

12.2 行列式のテクニック

14 二項係数のテクニック 30

14.1 頻出公式集

二項係数を経路数に帰着すると式変形が楽

15.1 対称性を用いる場合

15.2 DP を用いる場合

16 「解けない問題」を見極める