2020-2021:teams:wangzai_milk:weekly12
2020.07.18-2020.07.24 周报
团队训练
2020.07.18 2020牛客暑期多校训练营（第三场） prob:7:8:12 rnk:112/1175
2020.07.20 2020牛客暑期多校训练营（第四场） prob:4:5:10 rnk:60/1112
_wzx27
专题
做了点后缀自动机的题。
题目
牛客三
牛客四
比赛
Infinity37
专题
无
题目
牛客三
牛客四
比赛
Zars19
专题
题目
比赛
本周推荐
_wzx27
题目链接：Takahashi's Basics in Education and Learning
tag：矩阵快速幂 思维
题意：
给一个等差数列的首项 $A$ 公差 $B$ 和项数 $L$，把这 $L$ 项连接起来得到一个很长的整数。求这个数对 $M$ 取模的结果。
$1 \le L,A,B \le 10^{18}$
$1 \le M \le 10^9$
保证等差数列的每一项都不超过 $10^18$。
题解：
如果暴力维护答案就是 $ans = ans \times 10^{bits} + a_i$，这种线性递推式考虑用矩阵快速幂优化。
把 $L$ 项按照位数划分，对于每一组位数为 $\text{bits}$ 的项，都构造如下矩阵：
$$ \begin{bmatrix} 10^{bits} & 1 & 0 \\ 0 & 1 & B \\ 0 & 0 & 1 \end{bmatrix} $$
左乘矩阵
$$ \begin{bmatrix} ans \\ a_i \\ 1 \end{bmatrix} $$
2020-2021/teams/wangzai_milk/weekly12.1595509387.txt.gz · 最后更改: 2020/07/23 21:03 由 wzx27
