菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

这个月大概打了打学校公益课的入门赛。挑一些入门赛进阶组的题目写一写。

所有代码不保证包括无关紧要的部分

---

Second_1 I: Queuing (HDU 2604)

Problem

求满足以下性质的长为 $|s| \ (|s| \le 10^6)$ 的字符串 $s$ 的数量：

1. $s$ 中仅包含 $\texttt{f} / \texttt{m}$ 两种字符
2. $s$ 不含子串 $\texttt{fff}, \texttt{fmf}$。

答案对 $m \ (1 \le m \le 30)$ 取模。$T$ 组询问。

Solution

没有什么疑问地 dp 推一下式子。网上的博客的 dp 方法都太神仙学不会，自己在赛时只会最弱智的。

设 $f_{i, 0/1/2/3}$ 分别表示长为 $i$ 的字符串 $s$ 的最后两位是 $\texttt{ff}, \texttt{fm}, \texttt{mf}, \texttt{mm}$ 的方案数。

由此得显然的递推式

$$\begin{aligned} f_{i, 0} & = f_{i - 1, 2} \\ f_{i, 1} & = f_{i - 1, 0} + f_{i - 1, 2} \\ f_{i, 2} & = f_{i - 1, 3} \\ f_{i, 3} & = f_{i - 1, 1} + f_{i - 1, 3} \\ \end{aligned}$$

然后发现这题模数是不固定的，所以 $O(T |s|)$ 的暴力一看就过不去（

后面的操作就多少沾点魔术：

为了记号上的美观，令四元组 $(a_1, a_2, a_3, a_4)$ 表示 $a_1 f_{j, 0} + a_2 f_{j, 1} + a_3 f_{j, 2} + a_4 f_{j, 3}$。于是暴力向后推几项：

$$\begin{array}{ccc} j = i & & j = i - 1 & & j = i - 2 & & j = i - 3 & & j = i - 4 \\ (1, 0, 0, 0) & = & (0, 0, 1, 0) & = & (0, 0, 0, 1) & = & (0, 1, 0, 1) & = & (1, 1, 1, 1) \\ (0, 1, 0, 0) & = & (1, 0, 1, 0) & = & (0, 0, 1, 1) & = & (0, 1, 0, 2) & = & (1, 2, 1, 2) \\ (0, 0, 1, 0) & = & (0, 0, 0, 1) & = & (0, 1, 0, 1) & = & (1, 1, 1, 1) & = & (1, 1, 2, 2) \\ (0, 0, 0, 1) & = & (0, 1, 0, 1) & = & (1, 1, 1, 1) & = & (1, 1, 2, 2) & = & (1, 2, 2, 4) \\ (1, 1, 1, 1) & = & (1, 1, 2, 2) & = & (1, 2, 2, 4) & = & (2, 4, 3, 6) & = & (4, 6, 6, 9) \\ \end{array}$$

（由于表里出现了很多重复项，所以人脑记忆化一下很快就算出来了，不能算麻烦）

发现 $(4, 6, 6, 9) = (2, 4, 3, 6) + (1, 1, 2, 2) + (1, 1, 1, 1)$。于是令 $f_i = \sum \limits_{j = 0}^3 f_{i, j}$，则有 $f_i = f_{i - 1} + f_{i - 3} + f_{i - 4}$。

后面的事大概就大家都知道了，搞出个矩阵来快速幂完事。

$$\begin{bmatrix} f_n \\ f_{n - 1} \\ f_{n - 2} \\ f_{n - 3} \end{bmatrix} = \begin{bmatrix} 1 & & 1 & 1 \\ 1 \\ & 1 \\ & & 1 \end{bmatrix}^{n - 3} \begin{bmatrix} f_{3} \\ f_{2} \\ f_{1} \\ f_{0} \end{bmatrix}$$

其中 $f_0 = 1, f_1 = 2, f_2 = 4, f_3 = 6$。复杂度 $O(T \log |s|)$。

Second_1 J: Count (HDU 6470)

Problem

已知 $f_1 = 1, f_2 = 2, f_n = f_{n - 1} + f_{n - 2} + n^3$，求模意义下的 $f_n \ (n \le 10^{18})$。$T \ (T \le 10^4)$ 组询问。

Solution

矩阵快速幂处理常数项的板子题。把所有含 $n$ 的项用 $n - 1$ 表示，得到矩阵

$$\begin{bmatrix} f_n \\ f_{n - 1} \\ (n + 1)^3 \\ (n + 1)^2 \\ n + 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 1 \\ & & 1 & 3 & 3 & 1 \\ & & & 1 & 2 & 1 \\ & & & & 1 & 1 \\ & & & & & 1 \\ \end{bmatrix} \begin{bmatrix} f_{n - 1} \\ f_{n - 2} \\ n^3 \\ n^2 \\ n \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 1 \\ & & 1 & 3 & 3 & 1 \\ & & & 1 & 2 & 1 \\ & & & & 1 & 1 \\ & & & & & 1 \\ \end{bmatrix}^{n - 2} \begin{bmatrix} f_{2} \\ f_{1} \\ 27 \\ 9 \\ 3 \\ 1 \end{bmatrix}$$

总复杂度 $O(T \log n)$。

Second_1 L: Another kind of Fibonacci (HDU 3306)

Problem

已知 $A_0 = 1, A_1 = 1, A_n = xA_{n - 1} + yA_{n - 2}$。令 $S_n = \sum \limits_{i = 0}^n{ A_i^2 }$，求模意义下的 $S_n$。$(2 \le n, x, y < 2^{31})$。$T$ 组询问。

Solution

这题更是重量级。考虑推式子

$$\begin{aligned} A_n^2 &= x^2 A_{n - 1}^2 + y^2 A_{n - 2}^2 + 2xy A_{n - 1} A_{n - 2} \\ S_n & = S_{n - 1} + A_n^2 \\ & = S_{n - 1} + x^2 A_{n - 1}^2 + y^2 A_{n - 2}^2 + 2xy A_{n - 1} A_{n - 2} \\ A_n A_{n - 1} & = x A_{n - 1}^2 + y A_{n - 1} A_{n - 2} \end{aligned}$$

于是

$$\begin{bmatrix} S_n \\ A_n^2 \\ A_{n - 1}^2 \\ A_n A_{n - 1} \end{bmatrix} = \begin{bmatrix} 1 & x^2 & y^2 & 2xy \\ & x^2 & y^2 & 2xy \\ & 1 \\ & x & & y \end{bmatrix} \begin{bmatrix} S_{n - 1} \\ A_{n - 1}^2 \\ A_{n - 2}^2 \\ A_{n - 1} A_{n - 2} \end{bmatrix} = \begin{bmatrix} 1 & x^2 & y^2 & 2xy \\ & x^2 & y^2 & 2xy \\ & 1 \\ & x & & y \end{bmatrix}^{n - 1} \begin{bmatrix} 2 \\ 1 \\ 1 \\ 1 \end{bmatrix}$$

总复杂度 $O(T \log n)$。