数え上げテクニック集

数え上げテクニック集

• http://degwer.hatenablog.com/entry/20171220 DEGwer

• PDF

• 2 状態をまとめる

  • DPは全探索の高速化
    • 状態を同一視することで高速化する
    • まとめられる条件
      • 遷移先状態が同じ
      • 遷移につく係数が同じ
      • まとめられた状態すべてが問題文の条件を満たすか満たさないかのどちらか
    • ARC059F
    • codefestival_2016_final_F
    • AOJ2439

• 3 探索順の変更

  • 3.1 大きい順に並べる
    • AOJ2333
  • 3.2 順列は挿入DP
    • DPで順列を決める場合「何を既に使ったか」を管理する必要がある
      • 小さければbit DPという手もある
    • 並び順でやるのではなく、入れるものを昇順/降順でやる
  • 3.3 区間は終点でソート

• 4 条件の言い換え

  • 操作は多いが産物は少ない

• 5 greedy からの帰着

  • 「操作で作られる可能性のある列の個数を求めよ」は複数の操作列で同じ列が作られる時に難しい
  • 産物から操作列を一意に定める方法があれば数えやすくなる

• 6 場合分けのテクニック

  • パラメータで場合わけ
    • disjointになるように注意
  • AGC013D

• 7 線形和への分解

  • 僕が演算順序の変更と呼んでるものに近い
  • ビット演算を桁ごとに分解

• 8 部分群のテクニック

  • 操作が可逆で全域→部分群
  • ラグランジュの定理
  • 不変量の数の予想
    • 偶数なら偶奇の不変量がありそう

• 9 再帰的な定義の利用

  • DPと相性がいい　再帰的定義→DP
  • ARC037D

• 10 桁DP について

  • AOJ0570

• 11 高速化のテクニック

  • 11.1 累積和の利用
  • 11.2 データ構造の利用
    • フェニック木
  • 11.3 配列の使いまわし
  • 11.4 高速フーリエ変換
    • NTT
  • 11.5 高速ゼータ変換
    • 結合法則と交換法則を満たす演算に使える
  • 11.6 And と Add の畳み込み
    • 高速フーリエ変換と同様のアルゴリズム
  • 11.7 簡単な枝刈り

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

  • 12.1 二分累乗
    • AGC013E
    • コンパニオン行列の累乗
    • 多項式の累乗
  • 12.2 行列式のテクニック
    • 行列木定理
      • 全域木の個数
    • LGV公式
      • 非交叉経路の個数
    • https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf

• 13 小さい確率を無視する 29

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

  • 14.1 頻出公式集
    • 二項係数の公式
  • 14.2 経路数への帰着
    • 二項係数を経路数に帰着すると式変形が楽
  • 14.3 45度回転
    • XとYにわける
  • 14.4 カタラン数

• 15 包除原理 33

  • 15.1 対称性を用いる場合
    • AGC005D
  • 15.2 DP を用いる場合
  • 15.3 約数系包除
    • ARC064F

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