$4.10$ 比赛部分题解

$t1$ 暮色苍然

$Descroition$

$Solution$

由题意可以列出一点东西：
$$
\begin{cases}gcd(x, y) = a_1
\\gcd(x, y + 1) = a_2
\\gcd (x, y + 2) = a_3
\\\ldots
\\gcd(x, y + l - 1) = a_l
\end{cases}
$$
可以发现
$$
\begin{cases}
a_1|x, a_1 | y
\\a_2|x, a_2|(y + 1)
\\\ldots
\\a_l|x, a_l|(y + l - 1)
\end{cases}
$$
即
$$
\begin{cases}
y \equiv 0 \pmod{a_1}
\\y + 1 \equiv 0 \pmod{a_2}
\\\ldots
\\y + l - 1 \equiv 0 \pmod{a_l}
\end{cases}
$$
$exCrt$ 解方程，判断是否在 $n \times m$ 范围内即可。

特别的，对于 $k >= m$ 的情况，必然无解。

$t2$ 云外苍天

$Description$

$Solution$

先考虑没有折返限制的情况。

考虑根据点来 $dp$ ，设 $f[i][j][k]$ 表示从 $i \to j$ 转化了 $2^k$ 的方案数。

转移方程就是
$$
f[i][j][k] = \sum_{l = 1}^{n} f[i][l][k - 1] \times f[l][j][k - 1]
$$
跟弗洛伊德十分类似。

显然这个东西可以用矩阵优化。

然后考虑有了折返限制之后怎么搞。

有一个很巧妙的转化：把按点来转移改成按边转移。

然后就做完了。

建图就是先初始化邻接矩阵，然后转移矩阵就是能到 $A$ 的全部赋为 $1$ ，因为可以转移到其他点。

之后因为转移矩阵已经转移过一次了，乘上邻接矩阵的 $T - 1$ 次幂即可。

答案就是最后能到 $B$ 点的全部计入答案。

$t3$ 彼岸归航

$Description$

$Solution$

显然后面的所有列的状态都与第一列相关，只能是等于第一列或者与第一列完全相反。

所以考虑先搞出第一列，然后慢慢算。

可以将矩阵看成两个 $01$ 串，如果跟第一列相同的是 $0$ ，不同的是 $1$ 。

设 $f[i][j]$ 表示最大连续串长度为 $i$ ，当前连续串长度为 $j$ 的方案数。

转移方程就是
$$
f[i][j] = \sum_{k = 1}^{min (i, j)} f[i][j - k]
$$
很好理解，最大连续串长度为 $i$ 的串不可能当前会由连续长度 $i + 1$ 的串转移过来，当前连续串的长度也不可能是负数。

用前缀和优化一下这个东西，就 $O(n^2)$ 了。