题解：CF1874F Jellyfish and OEIS
BPG_ning
·
·
题解
平凡的花\
也会有梦想 惆怅\
也会有无奈和原谅\
多希望会有某个人\
为她的凋谢流泪和悲伤
牛牛牛！
考虑容斥，设你选出了钦定违法区间集合为 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 个，的答案。转移有：
g_{l,r,x}=g_{l,r-1,x-1}-\sum_{i=l}^{r} f_{i,r}\times g_{l,i-1,x}\times [r\leq m_i],
f_{l,r}=\sum_{x=0}^{n}x!\times g_{l,r,x}.
由于在转移 f_{l,r} 时 g_{l,r,x} 不考虑只选 [l,r] 的情况，所以在算出 f_{l,r} 后还要 g_{l,r,0}\gets -f_{l,r}。
时间复杂度 O(n^4)。