CF498E Stairs and Lines CF498E Stairs and Lines 肯定是状压，而且状压的就是轮廓线，我们考虑同时状压横着和竖着的情况。然后肯定需要进行矩阵快速幂复杂度还是很高的。 但是我们考虑我们当前位置和之前位置进行转移的时候使用的是竖着的线，而且横着的线仅仅在当前转移出现了，意味着肯定不会影响后面的计算。那么我们不妨枚举轮廓线，这样复杂度就是直接少了 $2^{7^3}$。 然后说几个细节，具体状态转移就自己推吧。我的写法是考虑当前位置和后面位置的衔接，对于也就是 $w_1$ 我们特殊处理一下 $w_0$ 也就是只有一个位置（存在竖线）是合法的。不然的话因为没有点所以只能是 $0$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697 ...

[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 names ...

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, +$ 两个操作是满足这个的。 别忘记构造单位矩阵。 ...