[HNOI2002]公交车路线 [HNOI2002]公交车路线 这题和没有一样。 直接按照题意建立转移矩阵即可。 笔者的答案矩阵是：$$\left[\begin{matrix}f_{A} & f_B & f_C & \dots & f_H\end{matrix}\right]$$其中 $f_i$ 表示经过了 $n$ 次操作从 $A$ 走到 $i$ 的方案数。 不妨设转移矩阵为 $G$。那么对于一个 $i \to j$ 的情况对应到转移矩阵中就是 $G(i, j)$ 。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <bits/stdc++.h>using namespace std;//#define Fread#define Ge ...

[SCOI2009]迷路 [SCOI2009]迷路 思考过程 这个东西发现距离只有 $9$，记得 $\tt Lcm(1 \dots 9) = 2520$ 那么直接考虑暴力处理出来，之后对于每个 $T$ 进行分开计算即可。 显然这个很难写，但是同样是因为距离是 $9$ 那么我们每次只能对于 $T$ 增加 $1$ 不妨考虑直接对于每个点拆开计算。 题解发现这个 $n$ 特别小，进行拆点矩阵快速幂，这里有几个细节就是因为是单向边，对于拆开的点肯定是距离小的连向距离大的。 这边给不是对于矩阵理解很清晰的神仙讲一下矩阵的细节： 笔者的写法是 $f_i$ 表示从 $0$ 开始到达点 $i$ 的方案数。 之后拆点之后也是如此，那么开始的矩阵就是：$$\left[\begin{matrix}f_{0, 1} & f_{0, 2} & \dots & f_{0, 9} & f_{1, 1} & \dots & f_{n - 1, 9}\end{matrix}\right]$$之后考虑转移系数矩阵 $G$，对于 $i \to j$ 的转移 ...

[NOI2013] 矩阵游戏 [NOI2013] 矩阵游戏 各位我是弱智石锤了。 题目可能不是很难但是有点细节要注意。 首先考虑行和列我们分别来看： 对于列的情况我们只需要前一项即可递推。 对于行的情况我们只需要上一项也可递推。 那么本质上题目就提示我们可以只保留一项进行矩阵快速幂。 不妨设答案矩阵是$$\left[\begin{matrix}1 & f_m\end{matrix}\right]$$我们考虑首先递推同一行之后再递推列，最后一行单独拿出来处理。$$\left[\left[\begin{matrix}1 & b \0 & a\end{matrix}\right] ^ {m - 1} \times\left[\begin{matrix}1 & d \0 & c\end{matrix}\right]\right] ^ {n - 1} \times\left[\begin{matrix}1 & b \0 & a\end{matrix}\right] ^{m - 1}$$注意 矩阵乘法不满足交换律，所以我们矩阵必 ...

[HNOI2011]数学作业 [HNOI2011]数学作业。 直接考虑 $\tt Dp$ 显然 $f_i = f_{i - 1} \times 10^{x} + i$。那么我们直接将其分段进行计算即可。 具体的矩阵：$$\left[\begin{matrix}1 & i & f_i\end{matrix}\right]$$ $$\left[\begin{matrix}1 & 1 & 0 \0 & 1 & 1 \0 & 0 & 10^x\end{matrix}\right]$$ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include <bits/stdc++.h>using ...

CF618G Combining Slimes CF618G Combining Slimes 首先考虑根据期望的线性性质对于每一个数分开来计算贡献，之后再求出每一个数出现的概率即可。 也不是很清楚这个东西是不是线性性质。 但是说实话就是对于所有数一起考虑是不能入手的。 之后我们发现事实上任意的数都有可能出现，发现其没有取模，我们不妨计算一下一个数可能出现的概率。 如果说这个数是 $x$，那么其概率是 $(1 - 10^{-9})^{2^{x - 1}}$。算一下发现 $x = 50$ 的时候这个东西基本上都趋近于 $0$ 了。那么我们可以直接只考虑前面的 $50$ 个数。 我们考虑算每个数至少出现一次的概率，那么设其为 $a(i, j)$ 那么可以得到转移方程：$$a(i, j) =a(i - 1, j - 1) \times a(i, j - 1)$$ 就是考虑前面出现的同时出现两个数的情况，那么肯定有一个拼成的数需要占用一个位置。 显然初值是 $a(1, 1) = p, a(1, 2) = 1 - p$。 但是发现 $n$ 实 ...

CF576D Flights for Regular Customers CF576D Flights for Regular Customers 没想到用 $\tt bitset$。 首先考虑肯定是对于 $d$ 排序一下进行计算。 我们维护一个矩阵表示其中 $a_{u, v}$ 表示是否存在 $u \to v$ 的路径。 我们需要求出对于一个时间 $t$ 可以到达哪些点，之后我们就在只有这些边的图上进行广搜即可。 注意我们的邻接矩阵是存图的，之后我们更新能到达哪些点的时候是用传递闭包更新的。不要把两个弄错了。 可以保证每个答案都会被计算到。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include <bits/stdc++.h>using ...

CF917C Pollywog CF917C Pollywog 发现 $x$ 是比较小的我们考虑直接状压。 之后发现 $n$ 是比较大的考虑使用矩阵加速进行运算。 矩阵加速其实不一定只能使用加减，使用 $\min, \max$ 也是可以的，具体来说需要满足一些性质。 我们不妨设这个两个运算符运算符是 $\oplus, \otimes$。 显然对于我们矩阵乘法的定义，最终得到的矩阵 $C(i, j)$ 肯定是通过 $(A_{i, 1} \otimes B_{1, j}) \oplus (A_{i, 2} \otimes B_{2, j}) \oplus \dots$ 得到的。 我们进行矩阵加速需要满足结合律，也就是 $(AB)C = A(BC)$ 我们直接拆开可以得到几个性质： $\otimes$ 满足交换律，结合律 $\otimes$ 对于 $\oplus$ 满足分配率，也就是说 $A \otimes(B \oplus C) = (A\otimes B) \oplus (A\otimes C )$ 显然对于 $\min, +$ 两个操作是满足这个的。 ...

P5303 [GXOI/GZOI2019]逼死强迫症 P5303 [GXOI/GZOI2019]逼死强迫症 说实在的这题不难，但是我推 $\tt Dp$ 的时候却只和正解相差一点，最后还是看了题解。 感觉平时练习的时候还是需要再耐心一点，可能再过一过就出来了呢？ 首先考虑 $\tt Dp$。 设 $f(i)$ 表示放了 $2 \times i$ 个方块，考虑不填 $1$ 的方块，那么答案就是 $f(i - 1) + f(i - 2)$。 如果填的话，我们考虑填的方法对于钦定了当前的位置的情况，另一边肯定是只有一种填法。而且对于中间的部分也是没有别的填法的，那么只有可能是在上一块填之前的位置。 我们考虑枚举上一块的位置：$$\begin{aligned}&\sum_{j = 1} ^ {i - 1} Fib(j - 1) \=& \sum_{j = 1} ^ {i - 2} Fib(j) \=& Fib(i) - 1\end{aligned}$$ 作者在这篇博客推导过这个结论。 可以发现递推式就是 ...