Spark Special dottle_dp note
解决问题：
-
分析问题性质
-
转化问题
-
用熟悉方法解决
要记住 OI 不是要你发明算法，只是要找方法！
"让我们揭露 dp 的本质"
1 容斥
容斥是一种很重要的思想，容斥的目标是转化问题。虽然，我们看似将问题转化复杂了，但是每一个子集的计算却变简单了（不必关心钦定集合外条件的满足与否），这是有些反常识的，所以这个技巧可能较难掌握。
例子一 $\gcd(a,b)=1\iff $ \(b\) 不为 \(a\) 的任何一个质因子的倍数
不满足……所有条件 \(\iff\) 全体减去满足……任何一个条件
2 状压 DP / 区间 DP
什么对后面的影响是重要的？
Q1
用于分析复杂度：经典问题拆分数
如果考虑顺序，那么这是一个简单的问题
那么如果有顺序，我们可以钦定其降序，但是这样不就要把结尾是哪个数加入状态了吗？？实际上只需要能够枚举全部状态空间即可，聪明的方法是设一个集合大小，转移两种：1.集合全部加1 2.集合插入一个1，容易说明该方法可以枚举全部集合
所以50的拆分数不会很多，所以状态数不很多
可以直接开 map<vector<int>,int>
状压就是把很多信息揉成一坨放进状态，数量只要不多，也可以放进map
养成分析状态数的习惯
Q2
容斥就是用来转化条件的
因为恰好不好做，改成弱序关系会好做一些，于是还要要求长度为 \(n\) ，所以求至少会好做一些，因为它的反条件是不经过，这个很舒服，然后套上容斥即可。
CF1572C
先列出有用的性质
区间 dp 呼之欲出
要么包含，要么不交
不要把区间 dp 做成板子，从来没有这么自然地设计过 dp
P4766
很难确定哪些外星人留下
我们找到了一个必须做的操作
子结构：把问题划分成若干相同不相干集合
其实很关键的是，要把这个东西画成一个图，意识到每个元素在两个维度方面的属性可以放到一个平面直角坐标系里
从值域上考虑，（例如最大值）会把序列分成两个部分
Q3
不要单增很好做，要了单增，如果普通地 dp，很难避免保存上一个位置是什么数。那么必须考虑以别的方式满足这个条件
这个贡献很奇怪 popcnt 是可以拆位贡献的，所以我们也考虑一位一位确定，这样，递增这个条件的表现就是，在第 \(m\) 位上，前面都是 \(0\) ，后面都是 \(1\) ，在第 \(m-1\) 位上，第 \(m\) 位为 \(0/1\) 的也是这样分段，就像把区间分成两半，每一半都是类似问题，考虑区间 dp
考虑从值域上进行 dp
1. 操作上的，要求包含或不交
2.值域上的，由于线性dp很难处理来自值域的影响，于是从值域上处理
3 树形 DP
如何保证写了对的树形背包
保证 siz 不要算多了
分析这一处的复杂度，即合并左右两个连通块的信息，发现循环次数就等于两边点对的数量，所以一个点对均摊 \(\mathcal O(1)\) ，而每个点对只会在 LCA 处贡献一次，所以总共是\(\mathcal O(n^2)\)
树的拓扑序计数
每个点都要在自己儿子的前面，在儿子构成的序列中，显然这个点在各个位置的方案数都是一样的，一共 \(siz_i\) 个位置 ，现在只要一种，即乘以 \(siz_i^{-1}\)
\[\frac{n!}{\prod siz_i} \]loj575
容斥，被钦定则取反，不被钦定则完全无要求
带容斥系数的意思就是，对于所有方案，满足的所有条件集合的容斥系数之和，这个东西其实就是原先原本容斥，把前面 \(i\) 个里面的全部钦定集合的满足方案都拆开来算总贡献，原来我们是一个集合一个集合地算总贡献，现在是一个方案一个方案地统计有几个集合。这个问题中，从前面转移就是枚举最后一段的钦定集合（就是最后一段所有大于），拼到前面所有钦定集合的后面，然后前面的一种集合就会多出来这一段，然后每一个方案的贡献会乘以组合数
就是这样的：
\[f_i=\sum_{S}(-1)^{|S|}|A_i(S)| \]其中， \(S\) 是在前 \(i\) 个中的一种钦定方案，\(A_i(S)\) 是在前 \(i\) 个数里满足 \(S\) 这个钦定方案的排列数量，如果设 \(l_i\) 是表示 \(S\) 中小于号连续段的长度，\(k\) 是钦定方案 \(S\) 中有多少小于号连续段的话，则：
\[|A_i(S)|={i\choose {l_1,l_2,\dots,l_k}} \]然后继承就是把前面所有 \(S\) 都加上最后一段的 > ，然后更新 \(|A_i(S)|\)
SAO
其实每个边都提供一条条件，全部满足的时候就是合法topo序
其实就是钦定有些向下边的条件被反转，其他都不考虑
拆贡献
\[\begin{aligned} &(a^2+b^2)(a+b)(a-b)\equiv k(a_i-a_j)\pmod p\\ \implies &a^4_i-ka_i\equiv a_j^4-ka_j\pmod p \end{aligned} \]神奇的拆乘法
乘法通常拆开做
P8555
只用知道相对大小，因为不需要什么差之类的
插入式 dp
其实就是先确定大小，然后往里面填数，他在填的时候，是相当于用一个变量名替代具体的数，然后把他插入到序列的位置
Paint O(N^3) 补充证明
命题 一段区间被染成端点的颜色一定是最优的
证明 考虑使得答案减少的操作，一定是帮助一对相同颜色的进行合并，此时会使得答案减少，但是端点处不可能在一对相同颜色之间，所以不可能产生这样的贡献，而且端点处可能可以形成一对相同颜色，修改会破坏这对相同颜色，所以必然不会更优，不动端点必不劣。故最后染成端点颜色必最优。
标签：值域,钦定,容斥,DP,集合,dp From： https://www.cnblogs.com/haozexu/p/18299321