如果没有其他限制，那么一个二元限制可能出现的方案数为 \(v^2\)。
考虑 \(\{x_n\}\) 的一个区间，设其中能放 \(t\) 个二元限制，它的左右端点有一元限制，求这 \(t\) 个限制的方案数。设这个数为 \(f(t)\)。
如果第一个二元限制的 \(a\) 与左端点 \(i\) 处的 \(x\) 值相同，那么对 \(x_{i+1}\) 有限制。由于 \(a\) 可以任取，所以方案数为 \(v\)，而还有 \(t-1\) 个二元限制，总方案数为 \(f(t-1)\times v\)。
如果第一个二元限制的 \(a\) 与左端点 \(l\) 处的 \(x\) 值相同，由于 \(n\ge 2\)，所以第二个数一定有方法和第二个二元限制的第一个数不同。以此类推，后面的只要不踩中二元限制的第一个数，都一定有方法把这个区间所有数全部填上。于是，只要第一个二元限制的第一个数与左端点的数不同，剩下的二元限制随便选，都一定是有解的。剩下 \(t-1\) 个二元限制的方案数为 \((v^2)^{t-1}=v^{2t-2}\)。但是第一个限制的 \(a\) 不能和 \(x_l\) 相同，于是总方案数为 \(v\times (v-1)\times v^{2t-2}=v^{2t}-v^{2t-1}\)。
综上，有
\[f(t)=v^{2t}-v^{2t-1}+v\times f(t-1) \]直接递推，时间复杂度 \(\mathcal{O}(n)\)。
进一步地，可以得到
\[f(t)=v^{2t}-v^{2t-k}+v^k\times f(t-k) \]代入 \(k=t-1\)
\[f(t)=v^{2t}-v^t+v^{t-1} \]于是可以 \(\mathcal{O}(\log n)\) 求 \(f(t)\)。
答案为所有一元限制之间区间的答案相乘。注意第一个和最后一个区间的答案都是 \(v^{2t}\)，因为二元限制是什么都没有关系。注意需要特判存在矛盾的一元限制。时间复杂度 \(\mathcal{O}(m\log n)\)。
标签：2t,限制,二元,NOIP,数为,times,2024,洛谷,第一个 From： https://www.cnblogs.com/NatoriBlog/p/18591091