---
tags: Programming Contest
---

# AtCoder Regular Contest 106 題解

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

## 心得

第一題竟然花了我 20 分鐘，還好最終有解出三題，排 872，積分 +87。

## A. 106

把所有可能爆開即可。一開始的想法是枚舉 b，然後用 `log`, `floor` 之類的函式的把對應的 a 找出來，但這個寫法會在 6 筆 test cases WA，debug 了好久找不出原因，八成是被 double 卡掉的關係。

ans = dict()
for a in range(1, 38):
    for b in range(1, 26):
        ans[pow(3, a) + pow(5, b)] = f'{a} {b}'

N = int(input())
print(ans.get(N, -1))

## B. Values

就看圖的各個連通區塊內的 A 值總和是不是 = B 值總和，因為連通區塊內的每個頂點可以互相交換值。

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    adj[u].append(v)
    adj[v].append(u)


def solve():
    vis = [False] * N
    for root in range(N):
        if vis[root]:
            continue

        vis[root] = True
        src, tgt = 0, 0
        stack = [root]
        while len(stack) > 0:
            u = stack.pop()
            src += A[u]
            tgt += B[u]
            for v in adj[u]:
                if not vis[v]:
                    vis[v] = True
                    stack.append(v)

        if src != tgt:
            return 'No'

    return 'Yes'


print(solve())

## C. Solutions

我嘗試造出二者不一致的情況，發現以下模式：


而這樣的模式使用 X 個線段，得到 M = 上排 - 下排 = (X - 1) - 1 = X - 2。所以限定 N 個線段時，能解出的最大 M 是 N - 2。當 M 小於 N - 2 時，就放 M + 1 個線段在上排，一個線段在下排（藍線），剩下的線段就讓他們不相交的放於下排（藍線）右邊。而 M < 0 的情況我實在找不出這樣的可能，所以就猜無解了。

一次過 `(~‾▿‾)~`，submit 時還以為會 WA。

N, M = map(int, input().split())

if M == 0:
    segs = [(2 * i + 10, 2 * i + 11) for i in range(N)]
    print('\n'.join([f'{l} {r}' for l, r in segs]))
elif 1 <= M <= N - 2:
    N_top = M + 1
    segs = [(2 * i + 10, 2 * i + 11) for i in range(N_top)]
    
    L, R = segs[0][0] - 1, segs[-1][1] + 1
    segs.append((L, R))

    N_rest = N - M - 2
    segs.extend((2 * i + R + 10, 2 * i + R + 11) for i in range(N_rest))

    print('\n'.join([f'{l} {r}' for l, r in segs]))
else:
    print(-1)

## D. Powers

那我們先解決一個問題：給定長度為 N 的陣列 A 與 B，求 $\sum_{i = 0}^{N-1} \sum_{j=0}^{N-1} A_i B_j$。我們可以利用分配律的特性，在 $O(N)$ 算出答案，因為所求等價於 $\left( \sum_{i=0}^{N-1} A_i \right) \left( \sum_{j=0}^{N-1} B_j \right)$。我們還可以推導出以下式子：

$$
\begin{align}
\sum_{0 \le i \lt N, 0 \le j \lt N} A_i B_j &= \left( \sum_{i=0}^{N-1} A_i \right) \left( \sum_{j=0}^{N-1} B_j \right)
\\
\sum_{0 \le i, j \lt N, i \ne j} A_i B_j &= \left( \sum_{i=0}^{N-1} A_i \right) \left( \sum_{j=0}^{N-1} B_j \right) - \left( \sum_{i=0}^{N - 1} A_i B_i \right)
\\
\sum_{0 \le i \lt j \lt N} A_i B_j &= \frac{\left( \sum_{i=0}^{N-1} A_i \right) \left( \sum_{j=0}^{N-1} B_j \right) - \left( \sum_{i=0}^{N - 1} A_i B_i \right)}{2}
\end{align}
$$

而這題就會用到上述的最後一個式子。讓我們將題目所求用二項式定理展開：

$$
\sum_{0 \le i \lt j \lt N} (A_i + A_j)^X =
\sum_{0 \le i \lt j \lt N} \sum_{k=0}^{X} {X \choose k} A_i^{X - k} A_j^k
$$

將二項式的部份往外提，再應用我們前面的式子。

$$
\begin{align}
&= \sum_{k=0}^{X} {X \choose k} \sum_{0 \le i \lt j \lt N} A_i^{X - k} A_j^k
\\
&=
\sum_{k=0}^{X} {X \choose k}
\frac{\left( \sum_{i=0}^{N-1} A_i^{X-k} \right) \left( \sum_{j=0}^{N-1} A_j^k \right) - \left( \sum_{i=0}^{N - 1} A_i^{X-k} A_i^k \right)}{2}
\\
&=
\frac{1}{2}
\sum_{k=0}^{X} {X \choose k}
\left(
\left( \sum_{i=0}^{N-1} A_i^{X-k} \right) \left( \sum_{j=0}^{N-1} A_j^k \right) - \left( \sum_{i=0}^{N - 1} A_i^X \right)
\right)
\end{align}
$$

如果我們預計算 $S_c = \sum_{i=0}^{N - 1} A_i^c, c \in [0, K]$，那上述式子就可以改寫成：

$$
\frac{1}{2} \sum_{k=0}^{X} {X \choose k} S_{X - k} S_k S_X
$$

此式可以在 $O(K)$ 時間求出。因此這題的整體時間為 $O(NK + K^2)$ 。

比賽時，我只想出了往外提的部份，沒想出後面 QQ。

#include <algorithm>
#include <atcoder/modint>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

using mint = atcoder::modint998244353;

template <typename T> struct CombTool {
    vector<T> fact;
    vector<T> finv;

    CombTool(int V) {
        fact = vector<T>(V, 1);
        finv = vector<T>(V, 1);
        for (int i = 1; i < V; i++) {
            fact[i] = fact[i - 1] * i;
        }
        finv[V - 1] = fact.back().inv();
        for (int i = V - 2; i >= 0; i--) {
            finv[i] = finv[i + 1] * (i + 1);
        }
    }

    T comb(int a, int b) { return fact[a] * finv[b] * finv[a - b]; }
    T perm(int a, int b) { return fact[a] * finv[a - b]; }
    T hcomb(int a, int b) { return comb(a + b - 1, b); }
};

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

    int N, K;
    cin >> N >> K;
    auto A = vector<int>(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    auto tool = CombTool<mint>(300 + 10);
    auto sum_of_pow = vector<mint>(K + 1, 0);
    sum_of_pow[0] = N;
    for (int i = 0; i < N; i++) {
        mint a = A[i];
        for (int c = 1; c <= K; c++) {
            sum_of_pow[c] += a;
            a = a * A[i];
        }
    }

    for (int x = 1; x <= K; x++) {
        mint ans = 0;
        for (int k = 0; k <= x; k++) {
            mint val = 0;
            val = val + sum_of_pow[x - k] * sum_of_pow[k] - sum_of_pow[x];
            val = val * tool.comb(x, k);
            ans += val;
        }
        ans = ans / 2;
        cout << ans.val() << endl;
    }

    return 0;
}

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