所有不可操作的点将整个字符串分为了若干个段,现考虑每一个点。
对于每个点来说,如果两边都无法操作,其对答案无贡献。
如果有一边可以操作,可以选择把这一边用其所在段替换,这会使所在段的可以自由操作的数少一。
如果两边都可以操作,此时既可以都为 \(0\),也可以都为 \(1\),这会使两边所在段的可以自由操作的数少一。
最后的策略是先考虑有一边可以替换的,再考虑两边都可以替换的。
证明一下。
由于每个点对答案的贡献相同,所以每种情况自身不用考虑枚举顺序。
对于第一种情况,其对后面无影响,而优先枚举第二种的剩余决策等价于第三种,因为每个点贡献相同。
所以贪心策略满足决策包容性,得证。
考虑相邻两个已经被限制的点,其方案数及化简如下:
\[\sum_{i=1}^{len-1} (v^{i-1}\times v\times (v-1)\times (v^2)^{len-i})+v^{len-1} \]枚举 \(i\) 的意义在于考虑前 \(i\) 个点被限制的情况,这时 \(i\) 前面的只能从一个固定点到另一个点,方案数为 \(v\)。
第 \(i\) 个点不能让下一个点被限制,方案数为 \(v\times (v-1)\)。
其后的点就随便选了,方案数为 \(v^2\)。
对于前 \(len\) 个点都被限制特殊考虑,此时最后一个点只有一种取法。
化简上述式子,最后化简为 \(v^{2\times len}-v^{len}+v^{len-1}\)。
对于前面和后面的点,也是随便选。
实现时注意可能出现重复的点。
标签:化简,一个点,数为,len,times,康复训练,考虑 From: https://www.cnblogs.com/HEIMOFA/p/18585054