-
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\)。