标签：DP 矩阵 计数 dp 优化 目录 解法
数え上げテクニック集 笔记。
引言
OI 中有三大专题：dp，数据结构，图论。而在这三大专题中，因为 dp 是从小问题的解法上升至大问题的解法的关键；所以 dp，在这三大专题中，优先性是第一位的。如果在从小问题的解法上升至大问题时，难免于时间和空间的超限，会使得这种题目值得深究；而在 OI 中，人们总是会深究简化所用时间和空间的方法，我们称这种方法为 dp 优化；而在这篇文章中，就会专门对那些耗费大量时间和空间的解法，处心积虑，找出对应的 dp 优化方法。
一、状态设计和简化（状態をまとめる）
二、设计转移顺序（探索順の変更）
1. 降序枚举（大きい順に並べる）
2. 在排列中插入（順列は挿入 DP）
3. 按照区间起/终点大小选择区间（区間は終点でソート）
三、改写条件（条件の言い換え）
四、结合贪心思想（greedy からの帰着）
五、根据事件找准参数（場合分けのテクニック）
六、求和问题（線形和への分解）
七、子群相关知识（部分群のテクニック）
八、递归定义的运用（再帰的な定義の利用）
九、数位 dp（桁 DP について）
十、dp 优化（高速化のテクニック）
1. 前缀和优化（累積和の利用）
2. 数据结构优化（データ構造の利用）
3. 利用之前的数组（配列の使いまわし）
4. FFT（高速フーリエ変換）
5. 高维前缀和/FMT（高速ゼータ変換）
6. 与卷积/FWT（And と Add の畳み込み）
7. 简单剪枝（簡単な枝刈り）
十一、矩阵的利用（行列を用いたテクニック）
1. 快速幂（二分累乗）
(1) 推导转移矩阵（行列の導出）
(2) BM 优化递推（？）（コンパニオン行列の累乗）
(3) 多项式快速幂（多項式の累乗）
2. 矩阵优化计数（行列式のテクニック）
十二、忽略小概率事件（小さい確率を無視する）
十三、二项式（二項係数のテクニック）
1. 常用公式（頻出公式集）
2. 转化为路径计数问题（経路数への帰着）
3. 旋转 45 度（45 度回転）
4. 卡塔兰数（カタラン数）
十四、容斥原理（包除原理）
1. 使用对称性（対称性を用いる場合）
2. 使用 dp（DP を用いる場合）
3. 对因数的容斥（約数系包除）
十五、“难解”的计数问题（「解けない問題」を見極める）
标签：DP,
矩阵,
计数,
dp,
优化,
目录,
解法
From： https://www.cnblogs.com/Fran-CENSORED-Cwoi/p/17052563.html