---
tags: Programming Contest
---

# AtCoder Beginner Contest 129 題解

## 心得

無事就來寫 atcoder。

## A, B, C, D

(⁎˃ᆺ˂)

## E. [Sum Equals Xor](https://atcoder.jp/contests/abc129/tasks/abc129_e)

$a + b = a \text{ XOR } b$ 意謂著 $a$ 與 $b$ 不能有共同的都是 $1$ 的 digit。這常常出現，要背起來！不能都是 1，也就是不會有進位。然後這題就可以用 [Digit Dp](https://hackmd.io/@amoshyc/rJtXgC_hw) 解了。

$$
\begin{array}{r}
&l_3 &l_2 &l_1 &l_0 \\
& a_3 &a_2 &a_1 &a_0 \\
& b_3 &b_2 &b_1 &b_0 \\
\end{array}
$$

在二進制中，設 $dp[i, f]$ = number of ($a_{i - 1} a_{i - 2}\cdots a_{0}$, $b_{i - 1} b_{i - 2} \cdots b_0$) such that

1. (f = 0) $a_{i - 1} a_{i - 2}\cdots a_{0} + b_{i - 1} b_{i - 2} \cdots b_0 \le l_{i - 1} l _{i - 2} \cdots l_{0}$
2. (f = 1) $a_{i - 1} a_{i - 2}\cdots a_{0} + b_{i - 1} b_{i - 2} \cdots b_0 \gt l_{i - 1} l _{i - 2} \cdots l_{0}$

枚舉第 $i$ 位 $a_i, b_i$ 所有可能情況，我們就可以遞推：

$$
dp[i, f] \to dp[i + 1, f']
$$

其中 $f'$ 代表 $a_i a_{i - 1} \cdots a_{0}+ b_i b_{i - 1} \cdots b_0$ 是不是大於 $l_i l_{i - 1} \cdots l_{0}$，而這只有有限幾種狀況而已。

mod = 10 ** 9 + 7
L = [int(c) for c in input()[::-1]]
N = len(L)

dp = [[0, 0] for _ in range(N + 1)]  # shaped [N + 1, 2]
dp[0][0] = 1

for i in range(N):
    for f in range(2):
        # a[i] = 0, b[i] = 0
        new_f = (L[i] == 0 and f == 1)
        dp[i + 1][new_f] += dp[i][f]
        dp[i + 1][new_f] %= mod

        # a[i] = 1, b[i] = 0
        new_f = (L[i] == 0) or (L[i] == 1 and f == 1)
        dp[i + 1][new_f] += dp[i][f]
        dp[i + 1][new_f] %= mod

        # a[i] = 0, b[i] = 1
        new_f = (L[i] == 0) or (L[i] == 1 and f == 1)
        dp[i + 1][new_f] += dp[i][f]
        dp[i + 1][new_f] %= mod

print(dp[N][0])

## F. [Takahashi's Basics in Education and Learning](https://atcoder.jp/contests/abc129/tasks/abc129_f)

首先我們有等差數列的遞迴型式：

$$
s_i = s_{i - 1} + B
$$

設 $t_i = s_0 s_1 \cdots s_i$ 的答案，彷造 [Horner's method](https://en.wikipedia.org/wiki/Horner%27s_method)，我們得到以下轉移：

$$
\begin{align}
t_i
&= 10^{digit(s_i)} t_{i - 1} + s_i \\
&= 10^{digit(s_i)} t_{i - 1} + s_{i - 1} + B
\end{align}
$$

$digit(s_i)$ 描述了 $s_i$ 是幾位數。我們可以將式子整理成矩陣型式：

$$
\begin{pmatrix}
t_i \\
s_i \\
1
\end{pmatrix}
= \begin{pmatrix}
10^{digit(s_i)} & 1 & B \\
0 & 1 & B \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
t_{i - 1} \\
s_{i - 1} \\
1
\end{pmatrix}
$$

如果式子中 3x3 矩陣的每一項都是定值，那我們可以透過矩陣快速幕求出答案 $t_{L - 1}$，但很可惜 $10^{digit(s_i)}$ 不滿足。

根據題意，因為 $A, B$ 都是正的，所以隨著 $i$ 增大， $digit(s_i)$ 只會單調遞增，而且題目又保證了 $s_i$ 最大只會是 10^18，所以有許多的相鄰的 $s_i$ 是相同位數！有相同位數的那些 $s_i$ 代表他們的 3x3 矩陣是相同的。以範測 [3, 7, 11, 15] 為例，我們可以寫出：

$$
\begin{pmatrix}
t_3 \\
s_3 \\
1
\end{pmatrix} =
\begin{pmatrix}
10^2 & 1 & B \\
0 & 1 & B \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
10^2 & 1 & B \\
0 & 1 & B \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
10^1 & 1 & B \\
0 & 1 & B \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
t_0 \\
s_0 \\
1
\end{pmatrix}
$$

先不考慮 mod，把數字填進去就會是：

$$
\begin{pmatrix}
371115 \\
15 \\
1
\end{pmatrix} =
\begin{pmatrix}
10^2 & 1 & 4 \\
0 & 1 & 4 \\
0 & 0 & 1
\end{pmatrix}^2
\begin{pmatrix}
10^1 & 1 & 4 \\
0 & 1 & 4 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
3 \\
3 \\
1
\end{pmatrix}
$$

也就是說，從 $t_0=3, s_0 = 3$ 開始，我們經過一次一位數的變換（得到 $t_1 = 37, s_1= 7$），然後有二次二位數的變換，來到 $t_3=371115, s_3 = 15$。我們把相同位數的那些變換都合併在一樣（如同上述公式中，二位數矩陣應有兩個，但被合併成平方），然後用快速幕求出。

接下來問題就是在 $s_i$ 序列中，有幾個一位數？幾個二位數？幾個 $d$ 位數呢？而這可以透過簡單的不等式求出：

$$
10^{d-1}\le s_i \lt 10^d
$$

最終，等式右邊最多只會有 18 個基底矩陣，因此時間完全來得及。實作上，就是建出這 18 個基底矩陣，並算出各要乘幾次，然後用矩陣快速幕將之乘出來。

def matmul(A, B, mod):
    N, D, M = len(A), len(A[0]), len(B[0])
    C = [[0 for _ in range(M)] for _ in range(N)]
    for r in range(N):
        for c in range(M):
            for i in range(D):
                C[r][c] += A[r][i] * B[i][c] % mod
                C[r][c] %= mod
    return C

def powmat(A, p, mod):
    N = len(A)
    ans = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        ans[i][i] = 1
    base = A
    while p:
        if p & 1:
            ans = matmul(base, ans, mod)
        base = matmul(base, base, mod)
        p >>= 1
    return ans


L, A, B, M = map(int, input().split())
pivots = [(10 ** d - A - 1) // B for d in range(1, 20)]

ans = [[A], [A], [1]] # t0, s0, 1
prev_pos = 0
for i in range(len(pivots)):
    if pivots[i] < 0:
        continue
    curr_pos = min(pivots[i], L - 1)
    cnt = curr_pos - prev_pos # number of transformation
    mat = powmat([[pow(10, i + 1, M), 1, B], [0, 1, B], [0, 0, 1]], cnt, M)
    ans = matmul(mat, ans, M)
    prev_pos = curr_pos
    if curr_pos >= L - 1:
        break
print(ans[0][0])

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::