P9400 题解

blog。很 naive 的题，写这篇题解，主要是现有题解都用的线段树 / 平衡树，让我感到很难绷。

一眼 DP。\(dp_{i,j}\) 表示前 \(i\) 个宿舍，现在有连续 \(j\) 个灯亮大于 \(B\)，方案数。

• \(dp_{i,0}=\max(\min(B, r_i) - l_i + 1, 0)\cdot\sum\limits_{j=0}^{A-1} dp_{i-1,j}\)。
• \(dp_{i,j}=dp_{i-1,j-1}\cdot\max(r_i-\max(B+1,l_i)+1,0)\)。初始化 \(dp_{0,0}=1\)。
• \(O(n^2)\)，期望 \(40\) 分。

这看起来随便优化啊！记 \(v_i=\max(r_i-\max(B+1,l_i)+1,0)\)。

• 处理 \(s_i=\sum\limits_{j=0}^{A-1} dp_{i,j}\)。你会 \(O(1)\) 算 \(dp_{i,0}\) 了。
• \(s_i=\sum\limits_{j=0}^{A-1} dp_{i,j}=dp_{i-1,0}+\sum\limits_{j=1}^{A-1} \Large(\normalsize dp_{i-1,j-1}\cdot v_i\Large)\normalsize=dp_{i-1,0}+v_i\cdot\sum\limits_{j=0}^{A-2} dp_{i-1,j}=\color{red}dp_{i-1,0}+v_i\cdot(s_{i-1}-dp_{i-1,A-1})\)。你会 \(O(1)\) 算 \(s_i\) 了。
• 观察红色部分，你只需要会算 \(dp_{i,0}\) 与 \(dp_{i,A}\)。
• \(dp_{i,A}=v_i\cdot dp_{i-1,A-1}=v_i\cdot v_{i-1}\cdot dp_{i-2,A-2}=\cdots=(\prod\limits_{j=i-A}^A v_j)\cdot dp_{i-A,0}\)。在线维护 \(\prod v_j\) 即可，可以边增加边用逆元删除。

综上你会线性了。注意数组越界，以及 \(0\) 没有逆元，请特殊处理。

code，时间复杂度 \(O(n)\)。（其实还要算上求逆元的复杂度，不管了）