Day 1
状压 DP
AT_dp_o
显然。
QOJ 9619
我们随机拆下式子：
\[\sum_{S} \varphi\left (\prod a_i\right ) = \sum_S \prod_{p|\prod a_i} \frac{p - 1}{p} \prod a_i
\]
预处理一个 \(h\)。
\[h_S = \prod_{p\in S} \frac{p - 1}{p}
\]
我们记 \(f_{S}\) 为总的答案，\(g_S\) 为当前 \(\sum\) 里面的那坨东西。然后转移：
\[g_{S\ \lor\ T} \leftarrow (f_S + g_S) a_i
\]
\[f_{S} \leftarrow f_S + g_S
\]
答案就是 \(f_S\times h_S\) 。
P1896
这题有很多种做法。
- 做法一，暴力。设 \(f_{i, j, S}\) 第 \(i\) 行放了 \(S\)，总共用了 \(j\) 个国王，\(\mathcal{O}( 4^n n^2)\)，精细实现 \(\mathcal{O}( 4^n n)\)。
- 做法二，上面的 \(S\) 转移时不交，所以枚举子补集 \(\mathcal{O}(3^nn)\)。
- 做法三，上面的 \(S\) 转移时状态数是斐波那契数列级别的，所以枚举子补集 \(\mathcal{O}(2.6^nn)\)。
- 做法四，轮廓线 DP，\(\mathcal{O}(2^{n + 1}n^2)\)。
P5074 \(/\) HDU1693
轮廓线 DP。
HDU6984
做法一：
- \(k \ge \sqrt{n}\) 按 \(\bmod k\) 去填，是 \(2^\frac{n}{k}\)。
- \(k\le \sqrt{n}\) 把最后 \(k\) 个压进状态里，暴力转移，有一个 \(2^k\) 的系数。
- 但是这个做法很不优，有些细节。
做法二：
- 我们换一种理解，把 \(1\sim k\) 分成一行，把 \(k + 1\sim 2k\) 分成一行，以此类推。
- 然后轮廓线 DP 来处理这个条件。
- 状态数只有斐波那数大小，可以更优秀的复杂度。
P4590
类似轮廓线，但是存的是 LCS 的 DP 数组，这种技巧被称为 DP 套 DP。
从前往后验证整个串的答案，类似自动机的思想来构造状态和转移。
数位 DP
P4127
经典数字和按同余。