?1的位置可以填 1 ? k 1-k 1?k的所有数問有多少种合法的方案,输出方案数
思路来源于官方题解,看完就是恍然大悟的感觉
这样就可以分奇偶两个串,相邻的两个数不相同
通过枚举可以发现,一个连续的 ? 1 -1 ?1串对答案的贡献只和 k k k以及左右两个数是否相等有关和左右两个数的具体值无关
0 0表示串左右两个数楿同 1 1 1表示左右两个数不同
比较懒,应该写个函数的直接复制了一遍
这是我做的时候随便写的样例,可以发现:
2.只有一边有约束的情况臨近约束的点有 k ? 1 k-1 k?1种选择,后面每个数都有 k ? 1 k-1
每一部分的贡献都是乘在 a n s ans ans上的(相互独立)