差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0609_abc129 [2019/06/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0609_abc129 [2019/06/12] – ikatakos | ||
---|---|---|---|
行 181: | 行 181: | ||
$L=1$ だったら、$S_1=A$ である。ここで、$S_k$ は初項・公差の条件が同じで $L=k$ の時の $S$ とする。 | $L=1$ だったら、$S_1=A$ である。ここで、$S_k$ は初項・公差の条件が同じで $L=k$ の時の $S$ とする。 | ||
- | $L=2$ なら $S_2$ は $(A)(A+B)$ をこの順に繋げた数だが、$A+B$ も3桁と分かっているならこれは $10^3A + (A+B)$ と数式で表現できる。 | + | $L=2$ なら $S_2$ は $(A)(A+B)$ をこの順に繋げた数だが、$A+B$ も3桁ならこれは $10^3A + (A+B)$ と数式で表現できる。 |
$L=3$ なら、$S_3=10^6A+10^3(A+B)+(A+2B)$ と表現できる。($A+2B$ も3桁の場合) | $L=3$ なら、$S_3=10^6A+10^3(A+B)+(A+2B)$ と表現できる。($A+2B$ も3桁の場合) | ||
行 189: | 行 189: | ||
さて、ここで、線形の漸化式は行列に変換できる。 | さて、ここで、線形の漸化式は行列に変換できる。 | ||
つまり、以下のように表せる。 | つまり、以下のように表せる。 | ||
+ | |||
+ | \[ | ||
+ | \left \{ | ||
+ | \begin{align} | ||
+ | S_i &=& 10^d \times S_{i-1} &+& 1 \times a_{i-1} &+& 0 \times 1 \\ | ||
+ | a_i & | ||
+ | 1 & | ||
+ | \end{align} | ||
+ | \right. | ||
+ | \] | ||
\[ | \[ | ||
行 284: | 行 294: | ||
first_d = len(str(a)) | first_d = len(str(a)) | ||
- | tail = a + b * (l - 1) | ||
lo = -1 # d桁未満となる最後の項が何番目か | lo = -1 # d桁未満となる最後の項が何番目か |