「Byakkai OI 2021」Eaquira | Alpha1022's Blog
Opened this issue · 0 comments
Alpha1022 commented
https://www.alpha1022.me/articles/byakkai-oi-2021-eaquira.htm
type = 1 算法 0 爆搜，不过只需要 (O(2^{2n}))（钦定绝妙极长连续黑区间段的过程的方案数是平凡的）。 算法 1 考虑一个 DP：设 (f(i,0/1,j)) 表示目前考虑到 (i)，(i) 所在区间是黑色 / 白色，(i) 所在区间所在极长连续黑区间段当前长度为 (j)（如果存在）的方案数。 转移时枚举 (i) 所在区间的开头即可。 首尾不同时取