---
tags: Programming Contest
---
# AtCoder Regular Contest 107 題解
[題目連結](https://atcoder.jp/contests/arc107)
## 心得
第二題鬼打牆，最終解出前三題，排 1245，積分 +35
## A. Simple Math
```python
A, B, C = map(int, input().split())
A = (1 + A) * A // 2 % 998244353
B = (1 + B) * B // 2 % 998244353
C = (1 + C) * C // 2 % 998244353
print(A * B * C % 998244353)
```
## B. Quadruple
上一次在 cf 有類似題我輕鬆解出，這次卻鬼打牆。比賽時就想到要枚舉 $a + b$ 然後算出 $c + d = K + (a + b)$，此時的方法數為 $f(a + b) * f(c + d)$，$f(x)$ 代表的是將 $x$ 分解成二個正整數的方法數。
問題就在於這個 $f$ 表要怎麼有效率的算出來，比賽時想了半天只想到用線段樹來事先建表，雖然也能 [AC](https://atcoder.jp/contests/arc107/submissions/17756889)，但明顯不是 intended solution。
賽後重新思考，發現是解聯立不等式，並可以 generalize：
**將整數 $x$ 分解成 2 個整數 $x = a + b$，且 $a_{min} \le a \le a_{max}, b_{min} \le b \le b_{max}$，問相異的 $(a, b)$ 有多少個？**
$$
min(x - a_{min}, b_{max}) - max(x - a_{max}, b_{min}) + 1
$$
解聯立不等式，合併前兩個式子：
$$
\begin{cases}
a + b = x \\
a_{min} \le a \le a_{max} \\
b_{min} \le b \le b_{max}
\end{cases}
\implies
\begin{cases}
x - a_{max} \le b \le x - a_{min} \\
b_{min} \le b \le b_{max}
\end{cases}
$$
可得 $b$ 的上下界：
$$
max(x - a_{max}, b_{min}) \le b \le min(x - a_{min}, b_{max})
$$
在此範圍內的 $b$ 都會有合法對應的 $a$。而 $b$ 的可能數量為「上界 - 下界 + 1」。
前述的 f 就是 $a_{min} = 1, a_{max} = N, b_{min} = 1, b_{max} = N$ 的特例，所以代公式即可。
```python
def f(x, a_min, a_max, b_min, b_max):
if x < a_min + b_min or x > a_max + b_max:
return 0
lb_b = max(x - a_max, b_min)
ub_b = min(x - a_min, b_max)
return ub_b - lb_b + 1
N, K = map(int, input().split())
ans = 0
for beta in range(2, 2 * N + 1):
alpha = beta + K
if 2 <= alpha <= 2 * N:
ans += f(alpha, 1, N, 1, N) * f(beta, 1, N, 1, N)
print(ans)
```
## C. Shuffle Permutation
觀察可以發現，可以將 rows 分解成一群一群的，例如第一筆範測 rows 就是分解成二群： [[0, 2], [1]]，群內的 rows 可以互相交換，所以 row 的方面可以有 2! * 1! 種變化。而 cols 也是一樣，第一筆範測的 cols 只有一群 [[0, 1, 2]]，3! 種變化。而 row 與 col 彼此獨立，所以得到 (2! * 1!) * (3!) = 12 的答案。第二筆範測的答案是 10! * 10!。
實作上就 O(N^3) 枚舉 + dsu 將各個群找出來。
```python
from collections import defaultdict
class DisjoinSet:
def __init__(self, N):
self.par = [-1] * N
self.sz = [1] * N
def root(self, x):
if self.par[x] < 0:
return x
else:
self.par[x] = self.root(self.par[x])
return self.par[x]
def unite(self, a, b):
a = self.root(a)
b = self.root(b)
if a == b:
return
if self.sz[a] > self.sz[b]:
a, b = b, a
self.par[a] = b
self.sz[b] += self.sz[a]
def same(self, a, b):
return self.root(a) == self.root(b)
def size(self, x):
return self.sz[self.root(x)]
def groups(self):
clusters = defaultdict(list)
for x in range(N):
clusters[self.root(x)].append(x)
return list(clusters.values())
N, K = map(int, input().split())
M = 998244353
A = [[int(x) for x in input().split()] for _ in range(N)]
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % M
row_dsu = DisjoinSet(N)
for r1 in range(N):
for r2 in range(r1, N):
if all(A[r1][c] + A[r2][c] <= K for c in range(N)):
row_dsu.unite(r1, r2)
col_dsu = DisjoinSet(N)
for c1 in range(N):
for c2 in range(c1, N):
if all(A[r][c1] + A[r][c2] <= K for r in range(N)):
col_dsu.unite(c1, c2)
cntR = 1
for group in row_dsu.groups():
cntR = cntR * fact[len(group)] % M
cntC = 1
for group in col_dsu.groups():
cntC = cntC * fact[len(group)] % M
print(cntR * cntC % M)
```
## D. Number of Multisets
這題與 [POJ 2229](https://gist.github.com/amoshyc/9b46373dfaeb9904ab65) 類似，但加了個數量為 N 的條件，因此 dp 也增一個維度，再根據這題調整。
P.S. 我 5 年前的題解，真的古老，原來五年來我根本沒什麼進步 (\~_\~;;;)
首先我們先把一些簡單數字的答案[爆出來](https://pastebin.com/XTZrLayB)，以下是 N = 6 時，K = 1 ~ 6 的組合方法：
```
6 :
1/1, 1/1, 1/1, 1/1, 1/1, 1/1
----------
5 :
1/1, 1/1, 1/1, 1/1, 1/2, 1/2
----------
4 :
1/1, 1/1, 1/1, 1/2, 1/4, 1/4
1/1, 1/1, 1/2, 1/2, 1/2, 1/2
----------
3 :
1/2, 1/2, 1/2, 1/2, 1/2, 1/2
1/1, 1/1, 1/2, 1/4, 1/8, 1/8
1/1, 1/1, 1/4, 1/4, 1/4, 1/4
1/1, 1/2, 1/2, 1/2, 1/4, 1/4
----------
2 :
1/1, 1/2, 1/4, 1/8, 1/16, 1/16
1/1, 1/2, 1/8, 1/8, 1/8, 1/8
1/1, 1/4, 1/4, 1/4, 1/8, 1/8
1/2, 1/2, 1/2, 1/4, 1/8, 1/8
1/2, 1/2, 1/4, 1/4, 1/4, 1/4
----------
1 :
1/4, 1/4, 1/4, 1/8, 1/16, 1/16
1/2, 1/4, 1/16, 1/16, 1/16, 1/16
1/2, 1/4, 1/8, 1/16, 1/32, 1/32
1/2, 1/8, 1/8, 1/8, 1/16, 1/16
1/4, 1/4, 1/8, 1/8, 1/8, 1/8
----------
```
以 K = 2 為例，他的 5 種分解方法可以拆成 2 部份：
含 1/1 的：
```
1/1, 1/2, 1/4, 1/8, 1/16, 1/16
1/1, 1/2, 1/8, 1/8, 1/8, 1/8
1/1, 1/4, 1/4, 1/4, 1/8, 1/8
```
與不含 1/1 的：
```
1/2, 1/2, 1/2, 1/4, 1/8, 1/8
1/2, 1/2, 1/4, 1/4, 1/4, 1/4
```
不含 1/1 的部份，把每一項都乘 2，就是 K = 4 時的組合。
其他數字也可以此類推，K = k 不含 1/1 的部份每項乘 2 就是 K = 2k 的組合。
這引導我們設計出：`dp[i, j]` = 將數字 j 分解成 i 個值的方法數。
考慮有含與沒含 1/1 的部份，得到轉移方程：`dp[i, j] = dp[i - 1, j - 1] + dp[i, 2 * j]`。
實作上小心計算順序：
```python
N, K = map(int, input().split())
M = 998244353
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
for j in range(N, 0, -1):
dp[i][j] = dp[i - 1][j - 1]
if 2 * j <= N:
dp[i][j] += dp[i][2 * j]
dp[i][j] %= M
print(dp[N][K])
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet