---
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/)
:::
Sign in with Wallet
Connect another wallet