-
Polygon
根据范围 dp 还是比较显然的。\(f_{i,j}\):将i边形分成j个多边形的方案数。
整体思考
一开始的方向是通过保证每种方案，对于每条分割线计算一次去重，对于每个状态的转移，枚举每条分割线，然后枚举两侧分割个数，对于分割线两侧获得多边形边数相同的情况特殊处理一下。问题在于最后要/(j-1)，不保证有逆元。
从变化/加入的角度考虑
于是考虑每种方案只计算一次，从i-1边形到i边形的角度考虑。
新加入的角编号为i，先考虑不用这个点的情况：1.连结其相邻两个点，贡献1，剩下为i-1边形；2.不连结其相邻两点，贡献0，多的这一块和剩下的拼起来。此时\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\)。再考虑使用这个点的情况：枚举顺时针起第一个与其相连的点，再枚举两侧分割的个数，其中一侧随便选，另一侧有不和i相连的限制，用类似上面的套路做。code -
PSequence
首先\(\bmod p\)分一下组，转化成不同组的不能相邻的排列数（s可能为负，坑）。先只考虑种类，再分配上去。发现直接组合不好做，注意到范围考虑dp。分完类，从逐个种类插入的角度考虑。\(p_i\)表示第i类的个数，\(f_{i,k}\)表示做完前i个种类，有k组同类相邻，转移枚举第i类相邻的合并之后的个数j，对于相邻个数有影响的可以这么考虑（4,2,2,1,2,3,2中2类该值即为3），破坏原有相邻相等数对的数量c。具体转移见code -
计算n个物品中不相邻地选若干个选法。
- 设\(f_i\)为i个，钦定选了i。$f_0=f_1=1 \(,\)f_i=\sum_{j=0}^{i-2} f_j \(,\)ans=\sum_{i=0}^{n}f_i$
- 设\(f_i\)为i个的答案，\(f_0=1,f_1=2,f_i=f_{i-1}+f_{i-2}\)
- 两种状态设法具有参考价值。分别是对边界作出直接限制和从原有状态添加考虑新的选或不选。
-
CF559C Gerald and Giant Chess
根据范围易得肯定是在黑点上做的。考虑容斥，ans=所有方案-经过黑点的。考虑如何不把经过黑点的算重，用首次去重的方法，\(f_i\)意义为经过的第一个黑点是i的方案数，转移也一样操作。code -
CF722E Research Rover 妙妙题。首先考虑期望=所有方案贡献总和/方案数，然后注意到贡献种数非常少，除了\(\log s\)次之后就一直是1了，（又是注意到答案取值少的性质啊！）。\(g_{i,j}\)表示经过了恰好i个点，现在到j的方案数，然后发现转移要数重，如果按上一个题的做法预处理两个点之间不经过某点方案数，变成\(O(n^3)\)。考虑改变状态意义，把恰好改成至少，差分容斥一下，\(g_{i,j}=f_{i,j}-f_{i+1,j},f_{i,j}=\sum (f_{i-1,k} - f_{i,k})\times coef(k \rightarrow j)\)。这样不会数重是因为钦定了第i-1个是不同的，感觉和通过首个避免算重相似。
-
P6275 [USACO20OPEN] Sprinklers 2: Return of the Alfalfa P
首先看出最后由一条从\((0,0)\)到\((n,n)\)的折线分割，在每个转折点都必须要安装，剩下的随意。总共有S个可安装的点，每种分割线有c个转折点，\(ans = \sum 2^{S-c}\)。注意到dp的目的是减少重复计算次数，每次我们只关心走到了哪个点、上一步横着还是竖着走，而不关心中间的步数，所以状态设计成\(dp_{i,j,0/1}\)表示走到点\((i,j)\)（而非格子），接下来的方向向下/右（注意这步向下/右的还没有走，省去了边界的判断）。转移的时候初始为\(2^S\)，后面拐一下\(\times inv_2\)即可。code （这个题可能还可以同时当作一个刻画折线的示范） -
P10259 [COCI 2023/2024 #5] Piratski kod 之前写过一个比较详细的找不到了/kk。把一个海盗代码拆成一个整块和一个散块。计算散块贡献，然后整块拆成已有整块拼上末尾为1的散块接上一个1。用到了首个防止算重的思想。
-
U111203 题面越来越短了 出现过 -> 1.钦定第一次出现位置（2.考虑钦定至少出现次数）
-
P12028 [USACO25OPEN] Moo Decomposition G 前面限制松，后面限制紧 -> 考虑从后往前做。证明划分不会跨串，考虑如果跨串，最后一个串会被用掉部分O（用M不可能和前面配对），那这个串就无解了。
- CF1332E Height All the Same 考虑一个初始局面可行的充要条件。考虑转化操作，发现单个+2不会改变奇偶性，所以从此角度考虑；相邻+1会同时改变两个奇偶性，并且叠起来做可以翻转任意两个。当\(nm \bmod 2 = 1\)时，奇偶个数必然一奇一偶，怎么放都成立，\(ans=(R-L+1)^{nm}\)。否则，奇偶个数必须均偶，\(ans=\sum_{2|i} C_{nm}^i \times {c_0}^i \times {c_1}^{nm-i}\)，\(c_0,c_1\)分别表示\([L,R]\)中的偶数、奇数个数。发现这个东西长得比较二项式定理（一开始想要把这个硬套二项式定理放到系数上去，但是我们的目的是把这个\(\sum\)消掉啊，系数没有任何作用，直接关于这个的柿子就行），但是只取了奇数项，一开始想把2都除掉，做不了啊！考虑把偶数项消掉，消掉要使用相反数，所以\(ans=\frac{(a+b)^{nm}+(a-b)^{nm}}2\)。