线性代数

7/19

[ABC189E] Rotate and Flip

题意：

给定在二维平面上的一些点，给定 \(m\) 次操作，为顺时针转 $\frac{\pi}{2} $，逆时针旋转 $ \frac{ \pi }{2} $，以某某对称轴对称，每次询问在 \(x\) 次操作后的某个点的坐标。

\(n,m,q \le 2 \times 10^{5}\)

由于每个操作是整体操作，所以我们存下整体操作即可，在询问时在讲点修改，由于每个操作都属于一个线性变换，那么我们用矩阵来维护这些变换 ，那么就是求个前缀和就行了比较ez的典题。

[TJOI2019] 甲苯先生的字符串

题意：

给定一个字符串 \(s1\)，要求构建长度为 \(n\) 的字符串 \(s2\) ，使得两个在 \(s1\) 相邻出现过的字符不能在 \(s2\) 相邻出现（有顺序），求在模 \(10^{9}+7\) 下一共能构造多少这样的字符串 \(s2\)。

\(n \le 10^{15}\)

\(len(s1) \le 10^{5}\)

数数题，先考虑 \(dp\)，\(f_{t,i}=\sum_{\left \{j,i\right \}\notin s1}^{} f_{t-1,j}\)，那么直接做显然\(O \left( 26^{2} n \right)\)，果断选择矩阵快速幂优化 \(dp\)，那么简单建一下矩阵就做完了，\(O \left( 26^{3}logn \right)\)。

[SDOI2010] 外星千足虫

题意：

有 \(n\) 个数 \(a_{i}\)，求这 \(n\) 个数的奇偶，\(m\) 个条件，每个条件给你 \(a_{k_{1}},a_{k_{2}},....,a_{k_{x}}\)的和的奇偶性，问你到第几个条件时就能判断所有数奇偶，以及所有数的奇偶，如果有多解即不能判断，输出 \(Cannot Determine\)。

\(n \le 10^{3}\)

\(m \le 2 \times 10^{3}\)

每个条件为 \(a_{k_{1}}+a_{k_{2}}+...+a_{k_{x}} \equiv p (mod 2)\)，我们可以想到异或是在二进制下不进位的加法，那么转换一下就是\(a_{k_{1}}\oplus a_{k_{2}}\oplus...\oplus a_{k_{x}}=p\) 那么我们得到了一个异或方程组。

由于异或符合交换律和结合律，因此可以用高斯消元得到解，我们只需要在找含第 \(i\) 项方程时发现没有方程组可找就是多解，找含项方程时最远到达的方程就是最早能判断全部奇偶的地方。

European Trip

题意：

给定一张 \(n\)个点，$ m $条边的无向图，（边的长度为 \(1\) ）求有多少条长度为 \(k\) 的路径，满足

\(\bullet\) 起点和终点相同
\(\bullet\) 不存在相邻两步走同一条边，即不存在 $ a\to b \to a$ 的路径

答案对 \(998244353\) 取模

\(3 \le n \le 100\)

\(k \le 10^{4}\)

没有限制怎么做？直接矩阵加速 \(dp\) 即可。

有限制怎么做？先考虑第一个限制，设 \(F_{t} \left ( i,j\right )\)为从 \(i\) 出发经过 \(t\) 时刻到达 \(j\) 的方案数，统计
\(\sum_{i=1}^{n} F_{k} \left ( i,i\right )\)。

不能连续走一条边，那么我们可以先求所有路径数，再减去连续走过同一条边的路径数，那么我们可以得到

$F_{t} \left ( i,j\right )=\sum_{p=1}^{n} F_{t-1} \left ( i,p\right )\times \left [ p\to j \right ] - F_{t-2} \left ( i,j\right )\times (deg_{j} -1 ) $

\(deg_{j}\)为度数，$F_{t-2} \left ( i,j\right )\times (deg_{j} -1 ) $是因为如果连续经过一条边，那么这条路在 \(2\) 个时刻前绝对在这个点上，然后每条路径都有度数\(-1\)种可能走法（为什么是度数\(-1\)，因为一条路径在之前已经走过一条边到这个点，那么不能再过这个点）。

那么我们建立一个 \(2n \times 2n\) 的矩阵，就行。

答案矩阵为\(\begin{bmatrix} F_{t} & F_{t-1} \\ 0 & 0 \end{bmatrix}\)

设 \(E\) 为边矩阵， \(I\) 为单位矩阵，\(D\) 为度数矩阵。

转移矩阵为\(\begin{bmatrix} E & I \\ D & 0 \end{bmatrix}\)

但是！当\(t=2\) 时，由于统计要减去的不合法的路径数时，点 \(i\) 在\(t-2\)时并不是从其他点转移过来，所以 $F_{t-2} \left ( i,j\right )\times deg_{j} $，度数并不需要 \(-1\)。