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}$$ 作者在这篇博客推导过这个结论。 可以发现递推式就是 $f(i) = f(i - 1) + f(i - ...

LOJ #10222. 「一本通 6.5 例 4」佳佳的 Fibonacci #10222. 「一本通 6.5 例 4」佳佳的 Fibonacci 首先直接对于这个题目不好入手，我们不妨看看题目中 $S(n)$ 是否有递推式，因为 $T(n) = \sum_{i = 1} ^ n S(n) - S(i - 1)$。 这个说实话挺显然的。 首先会想到 $S(n) - S(n - 1) = F(n)$ 但是这个没有什么作用，不过考虑 $F(n) = F(n- 1) + F(n - 2)$ 那么这个 $S(n)$ 是否也可以拆成这样类似的形式。 考虑 $S(n) = S(n - 1) + F(n)$ 之后我们考虑 $F(n)$ 能否拆分成若干个数的和，显然是可以的 $F(n) = F(n - 1) + F(n - 2)$，$F(n - 1) = F(n - 2) + F(n - 3)$ 那么最终的一项肯定是 $F(3) = F(2) + F(1)$ 其中多了一个 $F(2)$。 那么我们的狮子也是显然可以推出来了： $F(n) = S(n - 2) + 1$。 将这个柿子带入之前的 ...

CF1182E Product Oriented Recurrence CF1182E Product Oriented Recurrence 看到这个 $n$ 很大就会直接考虑矩阵乘法。 我们直接把指数拿下来即可，分成两部分进行计算。 对于 $c$ 的部分有这样的矩阵：$$\left[\begin{matrix}c_1 & c_2 & c_3 & 2n - 6 & 2\end{matrix}\right]\times \left[\begin{matrix}0 & 0 & 1 & 0 & 0 \1 & 0 & 1 & 0 & 0\0 & 1 & 1 & 0 & 0 \0 & 0 & 1 & 1 & 0 \0 & 0 & 0 & 1 & 1\end{matrix}\right]$$然后我们考虑每个数肯定是可以表示成 $c^xf_1^yf_2^zf_3^{\lambda}$ 这样的形式，我们对 ...

P3702 [SDOI2017]序列计数 P3702 [SDOI2017]序列计数 首先这个真的要骂一下自己，这个第一步显然就是正难则反。如果直接考虑进行 $\tt Dp$ 是否包含质数不是很方便我们可以直接使用容斥来做。 我们考虑正难则反进行计算，也就是计算总方案减去全部是合数的方案。 设 $dp(i, j, k)$ 表示考虑到第 $i$ 位，总和 $\mod p = j$ 是否有质数的方案。 之后考虑转移本质上就是枚举每一个数然后将之前的数加上这个数的贡献。 也就是 $dp(i, j) \to dp(i + 1, j + c)$ 。我们把这个 $j$ 当做上指标那么就是一个卷积的形式。 对于 $n$ 是 $10^9$ 级别我们直接进行快速幂即可，至于卷积可以直接暴力循环卷积。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798 ...

CF718C Sasha and Array CF718C Sasha and Array 重点： 矩阵乘法 $a\times(b + c) = ab + ac$。 而且矩阵乘法是有结合律的：$a \times b \times c = a\times (b\times c)$ 但是 $\color{red}\text{没有}$ 交换律！！ 发现这个下标的信息不是很好维护我们考虑将其放到矩阵里面进行维护。 也就是说我们需要维护一个权值和还有一个转移的矩阵。 对于一个区间加的操作对于整体区间都可以乘上一个转移矩阵。 我们考虑计算答案的时候直接维护一个答案矩阵即可。 具体来说不妨设初始矩阵为：$$\left[\begin{matrix}f_{i - 1}, f_i\end{matrix}\right]$$那么转移矩阵就是：$$\left[\begin{matrix}0 & 1 \1 & 1\end{matrix}\right]$$我们分别维护这两个量，每次下传标记的时候更新即可。 题外话： 我想的时候想到了矩阵，但是不知道为什么就是搞不懂要怎么维护。思路历程是这 ...

P5151 HKE与他的小朋友 P5151 HKE与他的小朋友 说实在的这个对于置换的理解需要略微深一点。 首先可以直接将其看成一个置换：$$\left[\begin{matrix}1 & 2 & 3 & 4 & 5 & \dots & n \a_1 & a_2 & a_3 & a_4 & a_5 & \dots & a_n\end{matrix}\right]$$这个的具体含义就是编号为 $i$ 的位置之后会变成 $a_i$。那么显然对于一个置换会有若干个置换环，我们直接对于每一个置换环进行处理即可，复杂度是 $O(n)$ 的。 最后我们再将其反过来即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;/ ...

$$\large\tt{bat} \text{ 之 } for \text{ 循环}$$ 你可以首先记一个东西叫：$\text{setlocal enabledelayedexpansion}$ 这个东西叫做变量延迟。 后面的东西可以看做 $3$ 个单词来拼起来，$\tt enable\ delayed\ expansion$。 然后常用的 $\tt for$ 貌似只有两种写法。 123for /l %%i in (a, b, c) do ( ) 还有一种就是 123for %%i in (a, b, c) do () 前面一种的意思就是从 $a$ 开始遍历到 $c$ 每次增加 $b$。 1for(int i = a; i <= c; i += b) 后面只是单纯遍历 $a, b, c$ 这几个数。 举个例子比如说我要创建 $0 \sim 9$ 的文件，同时里面各有其文件标号的数字。 1234@echo offfor /l %%i in (0, 1, 9) do (echo %%i > %%i.txt) 如果说是在 $0, 1, 9$ 的文件夹追加 $0, 1, ...