题解：CF1874F Jellyfish and OEIS

牛牛牛！

考虑容斥，设你选出了钦定违法区间集合为 $S$，容斥系数为 $(-1)^{|S|}$。

假设集合里存在两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 满足 $l_1<l_2\leq r_1<r_2$，那么显然 $[l_1,l_2-1],[l_2,r_1],[r_1+1,r_2]$ 都违法，所以区间 $[l_2,r_1]$ 选或不选，方案数一样，容斥系数抵消。所以只需要考虑 $|S|$ 中区间包含或不交的情况。

于是可以 dp 了：设 $f_{l,r}$ 表示区间 $[l,r]$ 违法，区间内方案的答案（不考虑 $[l,r]\in S$），再设 $g_{l,r,x}$ 表示区间 $[l,r]$ 内钦定了若干不交区间 $\in S$，没被区间限制的位置有 $x$ 个，的答案。转移有：

由于在转移 $f_{l,r}$ 时 $g_{l,r,x}$ 不考虑只选 $[l,r]$ 的情况，所以在算出 $f_{l,r}$ 后还要 $g_{l,r,0}\gets -f_{l,r}$。

时间复杂度 $O(n^4)$。