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, ...

高速对拍 看了一下机房里面的同学对于对拍基本上有几种写法： 直接用 $\tt c++$ 搞一个对拍 写 $3$ 个程序，之后用一个 $\tt bat$ 来整合 每次通过 $\tt bat$ 中的 $\tt <$ 进行传入随机种子（其实也就是拍了第几组），这个效率还是挺高的。 根本不屑于对拍 其中很多的写法都是 Sleep(1000)也就是意味着每秒最多只能对拍一次。 网上还有一种比较主流的写法，就是每次调用系统的内存，因为这个是动态的进行对拍。但是显然后者会有较大的可能重复导致效率不高。 于是就有了某些优秀写法： 12auto *it = new unsigned int;srand(time(0) ^ (*it)); 也就是每次取一个新的内存地址，然后和系统时间进行某些操作，可以尽可能保证其正确性。 说人话就是平时应该够用了。 但是有些时候对于一个程序不是很确定的时候，我们可以尝试使用更加有些的种子。 具体来说我们可以使用某些精度较高的种子： 12auto tm = std::chrono::high_resolution_clock::now();tm.tim ...