[题解][bzoj3269]序列染色

我们考虑枚举从左到右第一组连续k个B的起始位置和最后一组连续k个B的起始位置。
令f(i)左边以第i个位置为第一组连续k个B的起始位置时1~i中染色的方案数。我们可以使用容斥来求解。同理,右边是设为g(i)。
然后考虑合并即可。代码:

Tagged with:

发表评论