---
tags: Programming Contest
---

# AtCoder Beginner Contest 171 題解

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

## 心得

比賽中解出 5 題，排 2053，第三題卡了一段時間。這次前五題偏簡單，一堆人都解出五題，第六題又太難，輸在手速。

## A, B

略

## C. One Quadrillion and One Dalmatians

長度為 1 的字串的上下界是 [1, 26]。
長度為 2 的字串的上下界是 [27, 702]。
長度為 3 的字串的上下界是 [703, 18278]。
...

我觀察到的規律是 **每次的上界是前一次的上界加一再乘上 26**，這個上界指數型成長，所以給定 N，我可以快速地爆開所有的上下界，讓我知道答案是多長的字串。然後再推字母是哪些，即將 (N - 下界) 從 10 進制換成 26 進制。

def solve():
    N = int(input())

    lb, ub = 0, 0
    for n_digit in range(1, 100):
        lb = ub + 1
        ub = (ub + 1) * 26
        if lb <= N <= ub:
            off = N - lb
            res = []
            while off > 0:
                off, r = divmod(off, 26)
                res.append(r)
            while len(res) < n_digit:
                res.append(0)
            res.reverse()
            res = ''.join([chr(ord('a') + x) for x in res])
            return res
    
print(solve())

## D. Replacing

$O(QN)$ 肯定不行，自然而然就想到將序列存成**頻率數組**的型式，同時維護目前的序列和。

這題比賽時 TLE 了一次，因為 python `Counter` 的 `pop` 時竟然不是 $O(1)$，最後轉用 `dict` 寫就可以了。

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
ttl = sum(A)

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    
    if b in cnt:
        occ = cnt.pop(b)
        cnt[c] += occ
        ttl = ttl - b * occ + c * occ
    
    print(ttl)

## E. Red Scarf

看完題目還再三確認，這種題目一般是放在第二或第三題吧，就 xor 的基本性質：a xor a = 0, a xor 0 = a，這種題目八成是將給定的所有值 xor 在一起後再消掉一些，就如這題。

全部 xor 在一起的值，代表了答案的每項都被算了 N - 1 次在裡面，因為 N - 1 是奇數，也就是說答案的每項都被算了 1 次在裡面（偶數次對消），於是將此值與給定的每項 xor 一下，相同項對消，就能得到答案的各項。

N = int(input())
A = list(map(int, input().split()))

S = 0
for a in A:
    S = S ^ a

for a in A:
    print(S ^ a)

## F. Strivore

官方題解看不懂，網路上的也看不懂，直到看到[這篇使用重覆組合](https://kmjp.hatenablog.jp/entry/2020/06/21/1030)，雖然不懂日文，但在 google translate 的幫助下還是弄懂了。

以第一筆範測 `oof` 為例，假設 `K` 次操作後字串變成 `AoBoCfD`，其中 `A, B, C, D` 都是字串（可以是空的），一個重要的觀察是：

1. `A` 不能含有字母 `o`，要不然違反我們的假設，所以 A 只能用 25 種字母來填。
2. 同理 `B` 不能含有 `o`，只能用 25 種字母來填。
3. 同理 `C` 不能含有 `f`，只能用 25 種字母來填。
4. `D` 倒是可以隨便填。

因為 `D` 的性質與 `A, B, C` 不同，我們可以單獨處理 `D`，然後 `A, B, C` 一起做。現在的問題是我們不知道 `A, B, C, D` 的長度，但我們知道 `len(A) + len(B) + len(C) + len(D) = K`。我們枚舉 `D` 的長度，假設 `len(D) = L`，那 `len(A) + len(B) + len(C) = K - L`。`D` 的部份有 26 種字母，`A, B, C` 都有 25 種可以用，所以此時可產出相異字串數

$$
26^L \cdot 25^{K-L} \cdot H^3_{K-L}
$$

其中，$26^L$ 是 `D` 的方法數，$25^{K-L}$ 是 `A, B, C` 的方法數，$H^3_{K-L}$ 是代表 `len(A) + len(B) + len(C) = K - L` 的非負整解的個數。

這題實作上得使用 pypy 或 c++ 才能過，使用 python 會 TLE，以下為 pypy 的 AC Code：

K = int(input())
S = input()
M = int(10 ** 9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

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