# Panasonic Programming Contest 2020 Task E Three Substrings

2020/3/15

There is an arithmetic progression with $L$ terms: $s_0 , s_1 , s_2 , \dots , s_{L ? 1}$.

The initial term is $A$ , and the common difference is $B$. That is, $s_i=A + B i$ holds.

Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence $3 , 7 , 11 , 15 , 19$ would be concatenated into $37111519$ . What is the remainder when that integer is divided by $M$?

Constraints

• All values in input are integers.
• 1 ≤ L , A , B < $10^{18}$
• 2 ≤ M ≤ $10^9$
• All terms in the arithmetic progression are less than $10^{18}$.

From official editorial.
Paraphrasing the problem as follows

• We have two integers $X$ and $s$ written in base 10. Initially, $X=0$, $s=A$.
• In one operation, $s$ is appended to $X$, then incrase $s$ by $B$.
• After $N$ operations, calculate the value of $X \bmod M$.

Denote the number of $d$-digit elements as $C_d$, $C_d$ can be easily obtained by subtracting the number of elements below $10^{d}$ from the number of elements below $10^{d-1}$.

The operation of concatenating $C_d$ elements with $d$ digits to the end of $X$ is equivalent to repeating $(X, s) \mapsto (X imes 10d + s, s + B)$ $C_d$ times. And this operation can be reduced to a matrix product as follows.

(X, s, 1) \begin{pmatrix} 10^d & 0 & 0 \\ 1 & 1 & 0 \\ 0 & B & 1 \end{pmatrix}=(X imes 10^d + s, s + B, 1)

Therefore, the $C_d$ power of this 3 × 3 matrix needs to be obtained quickly, and the result is obtained with $O(\log C_d)$ time by the iterative square method.

If the above calculation is performed for $d=1, 2, \dots, 18$ in this order, the final value of $X \bmod M$ can be obtained quickly.

$2N$ 个格子（cell）排成一行，从左到右编号。每个格子是黑色或白色。现要进行 $N$ 次操作。每次操作选择两个编号不同的格子将二者之间（包括二者）的所有格子的颜色翻转。每个格子只能被选择一次。问有多少种方案使得最后所有格子都是白色。结果模 $10^9+7$ 输出。

Analysis

)

$R,G,B$ 能构成三角形的充要条件是 $R,G,B$ 中某个数大于等于 $S/2$ 。

Key observation: 最后剩下的小球最初所在的盒子必定是连续的一段。