---
# System prepended metadata

title: AtCoder Beginner Contest 179 題解
tags: [Programming Contest]

---

---
tags: Programming Contest
---

# AtCoder Beginner Contest 179 題解

[題目連結](https://atcoder.jp/contests/abc179)

## 心得

沒趕上比賽，只好賽後寫。

## A, B

(o´罒'o)

## C. A x B + C

差點就把質因數分解刻下去，後來想到用解不等式的方法即可在 $O(N)$ 時間解出。

我們可以枚舉 A 也枚舉 B，然後計算出 C，但這樣不夠快。
一個改進是：只枚舉 A，然後找出 B 的上下界，即 B 的合法範圍。

$$
0 < A \cdot B = N - C < N
\implies 0 < B < N / A
$$

加總所有的 A 對應的 B 的範圍即為答案。


```python
import math

N = int(input())
ans = 0
for A in range(1, N):
    lb = 1
    ub = math.ceil(N / A) - 1
    ans += ub - lb + 1
print(ans)
```

## D. Leaping Tak

大家應該都能想出這樣的 dp：

```
dp[i] = number of way to go from cell 0 to cell i
dp[0] = 1
for i in range(1, N):
    dp[i] = sum(dp[i - d] for d in [seg.l, seg.r] for seg in segs)
```

這題的問題是有太多 `d` 了，我們又需要加總的操作，於是就想到用線段樹或 BIT 來存 dp 陣列。


```python
mod = 998244353
 
 
class BIT:
    '''
    All methods use 0-based index while the internal use 1-based index
    '''
 
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
 
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            self.data[i] %= mod
            i += i & (-i)
 
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            res %= mod
            i -= i & (-i)
        return res
 
    def range_sum(self, l, r):  # [l, r]
        return ((self.sum_to(r) - self.sum_to(l - 1)) + mod) % mod
 
    def __str__(self):
        data = [self.range_sum(i, i) for i in range(self.N)]
        return '[ ' + ' '.join(map(str, data)) + ' ]'
 
 
N, K = map(int, input().split())
segs = [list(map(int, input().split())) for _ in range(K)]
 
bit = BIT(N, 0)
bit.add_at(0, 1)
for i in range(1, N):
    for (l, r) in segs:
        lb = max(i - r, 0)
        ub = i - l
        if ub >= 0:
            val = bit.range_sum(lb, ub)
            bit.add_at(i, val)
print(bit.range_sum(N - 1, N - 1))
```

## E. Sequence Sum

這題有兩種解法，一種是找循環，另一種是倍增法。

### 找循環

假設 A 的長度為 M + 1，我們可以宣稱裡面必有重覆的值，因為餘數只有 M 種可能。

有重覆的值代表序列會循環。於是我們可以將長度為 N 的 A 可以分成 3 個部份：

1. 進入循環前的部份，讓我們稱之 `prefix`
2. 不斷循環的部份，讓我們將重覆的部份稱為 `cycle`，其完整的循環次數為 `n_full_period`。
3. 剩下的部份，稱之為 `suffix`，會是 `cycle` 的前綴。

例如 `N, X, M = 7, 2, 1001` 時，`A = [2, 4, 16, 256, 471, 620, 16]`，可以分成：

1. `prefix = [2, 4]`
2. `cycle = [16, 256, 471, 620]`，`n_full_period = 1`
3. `suffix = [16]`。

讓我們找出這三個部份，再算各自會貢獻多少到答案中。
實作時，記得特判 `N < len(prefix)` 的情況，即還沒出現循環，序列 A 就結束了。


```python
import math

def solve():
    N, X, M = map(int, input().split())

    A = [X]
    vis = [-1] * M
    vis[X] = 0
    for i in range(1, M + 1):
        X = X ** 2 % M
        if vis[X] != -1:
            prefix = A[:vis[X]]
            cycle = A[vis[X]:]
            break
        A.append(X)
        vis[X] = i

    if N < len(prefix):
        return sum(prefix[:N])
    else:
        n_full_period = (N - len(prefix)) // len(cycle)
        suffix_length = N - len(prefix) - n_full_period * len(cycle)
        ans = 0
        ans += sum(prefix)
        ans += sum(cycle) * n_full_period
        ans += sum(cycle[:suffix_length])
        return ans

print(solve())
```

### 倍增法

能透過找循環解的題目八成都可以用倍增法來解，這題也不例外。

讓我們這樣定義：

```
nxt[i][r] = the value after 2 ** i squaring starting from r
dp[i][r] = the sum of sequence of length 2 ** i starting from r
```

其中 r 的範圍是 [0, M - 1]。這兩個陣列都能透過標準的倍增法 dp 在 $O(lgN M)$ 時間求出。有了這兩陣列，那我們就能透過對 N 進行二進位拆解，算出序列 A 的和。具體而言是將序列 A 拆成一些不重疊的部份，這些部份的長度正好是 N 的二進制拆解。例如：

```
N = 11 = 1 + 2 + 8
A = A[0:1], A[1:3], A[3:11]
Sum of each parts are:
sum(A[0:1]) = dp[0][A[0] % M]
sum(A[1:3]) = dp[1][A[1] % M]
sum(A[3:11]) = dp[3][A[3] % M]
```

其中我們知道 `A[0]` 是 `X`，`A[1]` 是 `nxt[1][A[0]]`，`A[3]` 是 `nxt[2][A[1]]`，以此類推。

```python
import math
 
N, X, M = map(int, input().split())
 
H = math.ceil(math.log2(N)) + 1
 
nxt = [[0] * M for _ in range(H)]
dp = [[0] * M for _ in range(H)]
nxt[0] = [r ** 2 % M for r in range(M)]
dp[0] = list(range(M))
 
for i in range(1, H):
    for r in range(M):
        nxt[i][r] = nxt[i - 1][nxt[i - 1][r]]
        dp[i][r] = dp[i - 1][r] + dp[i - 1][nxt[i - 1][r]]
 
ans = 0
r = X % M
for i in range(H):
    if N & (1 << i):
        ans += dp[i][r]
        r = nxt[i][r]
print(ans)
```

## F. Simplified Reversi

假設我們維護了兩種東西（0-based index）：

1. 每個 row 從左往右第一個遇到的白色棋子的 col，叫 `min_col_of_row`。
2. 每個 col 從上往下第一個遇到的白色棋子的 row，叫 `min_row_of_col`。

那每個 query 都可以高速地處理了。

當 query 為 `1 col`，此時共翻面 `min_row_of_col[col] - 1` 個黑色棋子。同時，row `1` ~ row `min_row_of_col[col]` 的 `min_col_of_row` 都變成 `col`（如果值比 col 大的話）。同理當 query 為 `2 row` 時，會有 `min_col_of_row[row] - 1` 個黑色棋子被翻面，然後影響到 col `1` ~ col `min_col_of_row[row]` 的 `min_row_of_col`。

於是我們想到使用二個 LazySegTree 來存這二種東西，這二個線段樹的更新不是一般的將某個區間設為某個值，而是將某個區間用某個值 'change min' 看看。這個方法的時間為 $O(NlgN + Q)$。

實作上，我使用之前不久 release 的 [atcoder library](https://github.com/atcoder/ac-library)。記得 submit 時，先用 `python expander.py main.cpp` 將 atcoder library 的 hpp 注入到 source code 中，要不然會 CE。

第一次使用 ACL，[document](https://atcoder.github.io/ac-library/document_en/lazysegtree.html) 中的 op, e, mapping, composition, and id 實在讓人搞不懂，我猜測了一下各自的作用，並將他們重新命名：我認為 S 指的就是 data 型態，F 是 lazy 的型態，5 個要求的函式分別為：

1. `S op(S a, S b)`：如何 gather。
2. `S default_data()`：data 的預設值。
3. `S apply_lazy(F lazy, S data)`：如何將 lazy 應用到 data 上。
4. `F push_lazy(F root, F child)`：如何將 root 的 lazy 推到 child 的 lazy，回傳 child 的 lazy。
5. `F default_lazy()`：lazy 的預設值。

希望沒有理解錯。最後抱怨一下 ACL 的線段樹不能丟 functor，只能丟 function pointer。

```cpp
#include <atcoder/lazysegtree>
#include <iostream>
#include <vector>

using namespace std;
using namespace atcoder;

using ll = long long;
using S = long long;
using F = long long;

S op(S a, S b) { return min(a, b); }
S default_data() { return S(1e10); }
S apply_lazy(F lazy, S data) { return min(lazy, data); }
F push_lazy(F root_lazy, F child_lazy) { return min(root_lazy, child_lazy); }
F default_lazy() { return F(1e10); }

using SegTree =
    lazy_segtree<S, op, default_data, F, apply_lazy, push_lazy, default_lazy>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    auto min_col_of_row = SegTree(N);
    auto min_row_of_col = SegTree(N);

    min_col_of_row.apply(1, N, N - 1);
    min_row_of_col.apply(1, N, N - 1);

    ll ans = (N - 2) * (N - 2);
    while (Q--) {
        int cmd, x;
        cin >> cmd >> x;
        x--;

        if (cmd == 1) {
            auto row = min_row_of_col.get(x);
            ans -= row - 1;
            min_col_of_row.apply(1, row + 1, x);
        } else {
            auto col = min_col_of_row.get(x);
            ans -= col - 1;
            min_row_of_col.apply(1, col + 1, x);
        }
    }
    cout << ans << endl;

    return 0;
}
```


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