Day 2
早上终于能稍微起晚一点了！拄拐走路真的好累啊Qw 走到餐厅胳膊都软掉了！
然后就记错了上课时间== 8:00开始8:30才到，顺便坑了——>的巨佬（超级超级抱歉QwQ！）
随手摸开题目，开始了Day 2的被吊打生涯Qw
（果然这边电脑也是有保护的啊=a今天是第二天不用VS Code打比赛了，大概有一点开始习惯Dev-C++了吧（不存在的(╯▽╰)））
T1 楼梯问题
对的我就是天泽龟博客里那个只会记忆化搜索拿70分的那个=x
贴一下70分代码
long long spilt_stair(long long s) {
long long ans = 0;
if (s == 0) return 1;
if (s < 0) return 0;
if (spi[s] != 0) { return spi[s]; }
for (long long i = 1; i <= m; i++) {
ans += spilt_stair(s - i) % MOD;
ans %= MOD;
}
spi[s] = ans % MOD;
return ans % MOD;
}
现在来介绍一下矩阵加速！
矩阵加速
1.从矩阵快速幂说起
矩阵乘法的定义是：设C = A * B，n为两个矩阵长度相等一边的长度，则$C_{ij} = \sum^{n}{k=1} A{ik} * B_{kj}。由此易得出矩阵乘法满足结合律，即(A * B) * C=A * (B * C)。那么矩阵的幂运算也可以使用快速幂，只是乘换为了矩阵乘。
此外，在矩阵乘法中，有一种特殊的矩阵，它的值为:\begin{bmatrix}
1 & 0 & … & 0 \
0 & 1 & … & 0 \
… & … & … & …\
0 & 0 & … & 1
\end{bmatrix}$
即除了对角线上的数字为1外其余皆为0的方阵，任何矩阵乘该矩阵结果均为原矩阵。我们称这个矩阵为单位矩阵，它的作用类似于整数乘法中的1.
下面贴代码：
struct Matrix {
int m[110][110];
int size;
Matrix() {
size = 0;
memset(m, 0, sizeof(m));
}
Matrix(int mode, int s) {
if (mode == 0) {
size = s;
memset(m, 0, sizeof(m));
}
if (mode == 1) {
size = s;
memset(m, 0, sizeof(m));
for (int i = 1; i <= size; ++i) {
m[i][i] = 1;
}
} //构造单位矩阵
}
Matrix operator*(Matrix& rhs) {
Matrix t;
int n = this->size;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
t.m[i][j] += this->m[i][k] * rhs.m[k][j];
}
}
}
t.size = this->size;
return t;
} //矩阵乘
void read(int s) {
size = s;
for (int i = 1; i <= size; ++i) {
for (int j = 1; j <= size; ++j) {
scanf("%lld", &this->m[i][j]);
}
}
}
void print() {
for (int i = 1; i <= size; ++i) {
for (int j = 1; j <= size; ++j) {
printf("%lld ", this->m[i][j]);
}
printf("\n");
}
}
}; //输出矩阵
Matrix fast_power_matrix(Matrix x, int n) {
Matrix ans(1, x.size);
while (n) {
if (n & 1) {
ans = ans * x;
}
x = x * x;
n >>= 1;
}
return ans;
} //矩阵快速幂
(直接复制粘贴的送你见祖宗哦=ω)
矩阵加速
讲完了矩阵快速幂，那么什么是矩阵加速呢？
对于a_{i}=a_{i-x}+a_{i-y}+a_{i-z}+…这样的递推式，我们可以构造一个矩阵\begin{bmatrix}
a_{i-x}\
a_{i-y}\
a_{i-z}\
…
\end{bmatrix}
联系上面所说到的知识，显然这里可以构造一个矩阵使上面的矩阵和构造的矩阵相乘得出以下矩阵：\begin{bmatrix}
a_{i}\
a_{i-x}\
a_{i-y}\
…
\end{bmatrix}
由此，我们可以用递推式开始的已知或易求得的几项组成的矩阵不断乘上一个构造的矩阵得到答案。又矩阵乘法的结合律可得，我们可以对构造的矩阵进行求幂运算，再乘上初始矩阵直接得到答案。
现在，以Luogu P1939为例，讲解矩阵如何进行构造。
本题的递推式为a_{i}=a_{i-1}+a_{i-3}，a_{1}=a_{2}=a_{3}=1，则得初始矩阵\begin{bmatrix}
a_{i-3}\
a_{i-2}\
a_{i-1}
\end{bmatrix}
现在我们要求的一个矩阵使初始矩阵乘上它为：\begin{bmatrix}
a_{i-2}\
a_{i-1}\
a_{i-3}+a_{i-1}
\end{bmatrix}
易得该矩阵为:\begin{bmatrix}
0&1&0\
0&0&1\
1&0&1
\end{bmatrix}
解释：
设\begin{bmatrix}
a_{i-3}\
a_{i-2}\
a_{i-1}
\end{bmatrix}与\begin{bmatrix}
0&1&0\
0&0&1\
1&0&1
\end{bmatrix}相乘得矩阵C，则
C_{11}=a_{i-3} * 0+a_{i-2} * 1+a_{i-1} * 0=a_{i-2}
C_{12}=a_{i-3} * 0+a_{i-2} * 0+a_{i-1} * 1=a_{i-1}
C_{13}=a_{i-3} * 1+a_{i-2} * 0+a_{i-1}*1=a_{i-3}+a_{i-1}=a_{i}
所以得到的矩阵C为\begin{bmatrix}
a_{i-2}\
a_{i-1}\
a_{i}
\end{bmatrix}。
接下来即可对结果进行计算，如求a_{i}:\begin{bmatrix}
1\
1\
1
\end{bmatrix} * \begin{bmatrix}
0&1&0\
0&0&1\
1&0&1
\end{bmatrix}^{i-3} = \begin{bmatrix}
a_{i-2}\
a_{i-1}\
a_{i}
\end{bmatrix}
3.本题的解法
根据上面的70分递推程序，易知本题递推式为：
ans_{i}=ans_{i-1}+ans_{i-2}+…+ans_{i-m}，ans_{0}=1，显然可以使用矩阵加速。
构造矩阵:\begin{bmatrix}
0&1&0&…&0\
0&0&1&…&0\
…&…&…&…&…\
0&0&0&…&1\
1&1&1&…&1
\end{bmatrix}
计算出ans_{1}…ans_{m}，使用上面的算法计算即可。
T2 数独
本场最水没有之一！！！（可惜忘了给Merge操作加可持久化爆炸了只有70分）
注意到操作数T \leqslant 100，直接开数组暴力模拟即可。注意细节，如各种操作时对历史数组的修改。
T3 疏散演习
学了一手求树的重心！
本题要求的是树的双重心，此处的处理方法是枚举边，将原树断裂成两棵新树，再分别计算重心即可。时间复杂度为O(n^{2})，可得50~60分。
对该算法进一步进行优化。
根据CSYZ的巨佬的说法，今天的题目基本达到提高组Day 1难度，蒟蒻今天也是第一次有了分数（140），心疼一下ouuan大佬Qw
下午不知为啥讲题咕咕咕了1.5hr 然后就见到了初三北大降一本爷CSYZ1（也是本场唯一AC T3的选手%%%）和另两位巨神。等待期间AC了Luogu P3390和Luogu P2024（理论上来说应该100AC了但洛谷显示还是99== 现在100AC了！ 晚自习更新：用矩阵加速写完了第一题！顺便AC了Luogu P1939与Luogu P1962）。