2020.07.18 2020牛客暑期多校训练营（第三场） prob:7:8:12 rnk:112/1175

20200718比赛记录

2020.07.20 2020牛客暑期多校训练营（第四场） prob:4:5:10 rnk:60/1112

20200720比赛记录

做了点后缀自动机的题。

牛客三

牛客四

Atcoder Beginner Contest 127 (VP)

Atcoder Beginner Contest 128 (VP)

无

牛客三

牛客四

cfr659 div2_infinity37比赛记录

20200719 - 一些非常简单的计算几何扫描线题

Codeforces Round 658 (Div. 2) Zars19

题目链接：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} $$