ARC-106
AtCoder Regular Contest 106
最近一直被ZCK推坑，vir了好幾場ARC
然後打完AGC才發現自己rating太低unrated，爛死XD
結果打完這場還是不到能夠rated的標準1200 QQ
然後想說寫一下題解好了 :P
A. 106
Statement
給你$N$，問你有沒有正整數$A,B$使得$3^A+5^B = N$，$N \leq 10^{18}$
Solution
因為$A,B$最多都是$\log$量級的所以亂枚舉就好了
基本上也不太會溢位
AC CODE
B. Values
Statement
給你一張無向圖，還有每個點一開始寫的數字$a_i$
每次可以把兩個相鄰的點$x,y$一個數字+1一個數字-1
問你是否能讓最後第$i$個點寫的數字是$b_i$
$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$-10^9 \leq a_i, b_i \leq 10^9$
Solution
只要一個連通塊裡$a_i$的總和和$b_i$的總和相同就做的到
於是用 dsu 維護總和
AC CODE
C. Solutions
一開始想說這題題敘很長先跑去做 pD
結果是水題，不過還是WA慘QQ
Statement
「給你$N$個線段，請選出最多條兩兩完全不相交的線段。。」
現在有兩種演算法$A,B$分別嘗試解決上述問題：
- $A$演算法：按照右界由小到大排序，並按照順序考慮線段。如果現在考慮的線段不會和當前的解的任何一條相交，則將其加入當前的解中。輸出最後的解的大小
- $B$演算法：按照左界由小到大排序，並按照順序考慮線段。如果現在考慮的線段不會和當前的解的任何一條相交，則將其加入當前的解中。輸出最後的解的大小
請構造一組輸出使得「$A$輸出的答案 - $B$輸出的答案 = $M$」
注意你構造的線段端點必須是不大於$10^9$的正整數，而且全部相異
$1 \leq N \leq 10^5$
$-N \leq M \leq N$
Solution
因為$A$演算法會是這個問題的最佳解，所以$M<0$是無解
首先$B$演算法一定至少會拿一個線段，所以$M=N$一定無解
$M=N-1$的話表示有一個拿所有線段的解，也就是所有線段都不相交，$B$會和$A$有同樣的輸出，也是無解
對於$0 \leq M < N-1$的case，先構造$N-1$條完全不相交的線段，接著考慮把剩下來的那條當作左界最小的，讓他和後面$N-1$個線段中的前$M+1$條相交，於是$A,B$演算法的輸出將會相差$M$
我在賽中一開始沒注意到$N = 1$的case，特判$N = 1, M = 0$才AC QQ
AC CODE
D. Powers
Statement
給你長度$N$的序列$A = (A_1,A_2,\dots,A_N)$以及$K$
對於所有$1\leq X\leq K$
請輸出$\left( \sum\limits _ {i=1}^{N-1}\sum\limits _ {j=i+1}^N (A_i + A_j) ^ X \right) \pmod{998244353}$
Solution
煩躁推式子
我不擅長QQ花好久
首先$\sum\limits _ {i=1}^{N-1}\sum\limits _ {j=i+1}^N (A_i + A_j) ^ x = \frac{1}{2}\left(\sum\limits _ {i=1}^N\sum\limits _ {j=1}^N (A_i + A_j) ^ X - \sum\limits _ {i=1}^N (2A_i)^X \right)$，先把$i < j$的條件拔掉
然後發現
$$
\sum _ {i=1}^N \sum _ {j=1}^N (A_i + A_j)^X = \sum _ {i=1}^N \sum _ {j=1}^N \sum _ {p=0}^X \binom{X}{p} A_i^p A_j^{X-p} = \sum _ {p=0}^X \binom{X}{p} \left( \sum _ {i=1}^N A_i^p \right) \left( \sum _ {i=1}^N A_i^{X-p} \right)
$$
對於$0\leq p\leq K$預處理$\sum\limits _ {i=1}^N A_i^p$就能$K^2$算出來了，總時間複雜度是$\mathcal{O}(NK+K^2)$
AC CODE
後面都是賽後才寫出來的題目QQ我就爛
E. Medals
我覺得這題真的很有趣，沒寫出來好可惜
Statement
有$N$個員工，以今天為基準，第$i$個員工會先工作$A_i$天，接著放假$A_i$天，又工作$A_i$天、放假$A_i$天，周而復始。
每天會頒發一個獎牌給有來工作的其中一個員工。當然如果當天沒有員工來工作就不會頒發任何獎牌。
現在想請問你，在最佳的情況下，最少要多少天，才能讓所有員工都得到至少$K$面獎牌？
$1 \leq N \leq 18$
$1 \leq K \leq 10^5$
$1 \leq A_i \leq 10^5$
Solution
最近才vir到一場需要Hall’s theorem的題目XD馬上就用到
我的解是考慮對答案二分搜
對於一個固定的天數$D$，想像一張有$D+NK$個頂點的二分圖，兩部份分別代表每一天以及每個人的$K$個獎牌，並且如果該天可以頒給那個人獎牌就連一條邊，那麼我們想要知道的就是是否有一個大小$NK$的匹配。
假設$A$是$NK$個頂點中的一個subset，$\Gamma(A)$是其鄰居，包含一些代表天數的頂點
那麼，根據Hall’s theorem，有那樣的完美匹配若且唯若$\forall A, |A| \leq |\Gamma(A)|$
不失一般性只需要枚舉$2^N$種組合，因為代表同一個人的頂點選再多個都不會影響鄰居的集合
接下來就是我因為不熟而沒在賽中寫完的部份QQ
為了對於所有subset都確認不等式的條件，我們必須知道有多少天會影響到這個subset的點
注意答案最多是$2K\sum A_i$，因此可以預處理每天可以對應到的鄰居
假設$Cnt_s$代表在$D$天內有多少天對應到$s$這個subset，以及$Day_s$代表有多少天會影響到$s$這個subset
那麼
$$
Day_s = \sum _ {t \& s \neq 0} Cnt_t
$$
用SOS DP或是被稱為Fast Zeta Transform的技巧可以在$\mathcal{O}(N2^N)$的時間複雜度內計算。
總時間複雜度是$\mathcal{O}((C+N2^N)\log C)$，其中$C = 2K\sum A_i$。聽說$C$可以壓到$\mathcal{O}(NK)$不過我不太會OAO
AC CODE
F. Figure
Statement
有一個玩具有$N$個零件，還有$N-1$個連接部件
第$i$個零件上面有$d_i$個孔
每個孔只能和一個連接部件連接，每個連接部件可以透過孔連接兩個零件
問你有多少不同的連接方式把所有零件組裝在一起。
注意零件上面的孔是相異的，但是所有連接部件都是相同的。
也就是說，兩種連接方式$T_1, T_2$相同，若且唯若所有在$T_1$中的連接部件$e_1$，在$T_2$中都有對應的$e_2$，兩端的零件編號以及孔編號完全相同。
Solution
我們將會介紹一種方法計算完全圖的生成樹有幾種，並且仿照該方式計算此問題的答案。
- 假設$N$個點的完全圖有$X$個生成樹。對於某個生成樹，可以任意定一個點當作根，並且把$N-1$個邊加上編號，這樣的方式總共有$X \times N \times (N-1)!$種。
- 用另一種觀點來看邊有標號的有根樹數量。每一步我們加上一條有向邊，考慮加邊加到現在的生成森林，這一步加上去的有向邊的起點可以是任何一個點，但是終點必須是某個連通塊的根，而且不能是同一個連通塊。也就是說，在第$i$輪有$N \times (N-i)$種選擇，因為除了自己以外的連通塊有$N-i$個。於是總方法數是$\prod\limits _ {i=1}^{N-1} N (N-i) = N^{N-1} (N-1)!$
- $X \times N \times (N-1)! = N^{N-1} (N-1)! \Rightarrow X = N^{N-2}$
同樣地，我們先假設本題的答案是$X$，並且令$S = \sum d _ i$
- 考慮某種連接零件的方式，並且把$N-1$個邊加上編號，這樣的方式總共有$X \times (N-1)!$種。
- 首先，先在每個零件選擇一個特殊孔，大致上是負責當作那個點和他的父節點連接的孔。在前$N-2$步，我們每次加上一條邊，其中一個端點可以是任何還沒用過的孔，但是不能是特殊孔；而另一個點必須是某個連通塊的根的特殊孔。這樣在第$i$輪有$(S - N - i + 1) \cdot (N - i)$種方法。最後一步，剩下兩個連通塊，我們把他們的特殊孔連在一起。這樣有$\prod\limits d _ i \cdot \prod\limits _ {i=1}^{N-2} (S - N - i + 1) (N - i)$種方法。
- 故 $X = \prod\limits d_i \prod\limits _ {i=0}^{N-3} (S - N - i)$
這題是我跑去找別人的解QQ
我看了好多解，好像都有用到Cayley定理甚至生成函數之類的QAQ好噁心
找了好久最後看到官方youtube的講解才聽懂
總結
這次有點可惜沒做出E QQ
然後看別人blog的時候驚訝他怎麼那麼厲害orz
希望某次有機會破台ARC