NOIP2024 T2题解

· · 题解

NOIP2024 T2题解

本场比赛最简单的题。

乍一看很像神秘图论，但是可以发现每个限制只和相邻两个数有关，每个数具体是什么也是不重要的，只要同个位置的一元限制的值相同即可。我们这里的被限制是指该变量被限制为一个固定的值。而且若对于相邻三个数 (x,y,z)，若 (x,y) 的二元限制没有限制 y 且 y 没有被一元限制，则对于任意 (y,z) 的二元限制一定存在一个 y 使得 z 不被限制。

于是我们可以设计 dp 状态，f_i 和 g_i 分别表示考虑完前 i 个变量，第 i 个是否被限制时前面限制的方案数。容易得到转移：

对于有一元限制的 i，f_i=f_{i-1}(1+v(v-1))+g_{i-1}v^2,g_i=0。

对于没有一元限制的 i，f_i=f_{i-1}v,g_i=f_{i-1}v(v-1)+g_{i-1}v^2

将转移用矩阵表示。

有一元限制：\begin{bmatrix}f_i&g_i\end{bmatrix}=\begin{bmatrix}f_{i-1}&g_{i-1}\end{bmatrix}\times\begin{bmatrix}v^2-v+1&0\\v^2&0\end{bmatrix}

没有一元限制：\begin{bmatrix}f_i&g_i\end{bmatrix}=\begin{bmatrix}f_{i-1}&g_{i-1}\end{bmatrix}\times\begin{bmatrix}v&v^2-v\\0&v^2\end{bmatrix}

然后直接矩阵快速幂即可，每个限制点乘上面的矩阵，相邻两个限制点直接乘下面的矩阵的若干次方。

注意 0 和 1 之间没有限制矩阵，初始条件的矩阵是 F_1，若 1 位置有被限制则是 \begin{bmatrix}1&0\end{bmatrix}，否则是 \begin{bmatrix}0&1\end{bmatrix}，最后的答案是 f_n+g_n 。

基本没啥细节，代码非常好写好调（等赛场代码发了再放）。

时间复杂度 O(Tm\log n) 。

复杂度是对的，卡常就有点过分了。