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

我們將會介紹一種方法計算完全圖的生成樹有幾種,並且仿照該方式計算此問題的答案。

  1. 假設$N$個點的完全圖有$X$個生成樹。對於某個生成樹,可以任意定一個點當作根,並且把$N-1$個邊加上編號,這樣的方式總共有$X \times N \times (N-1)!$種。
  2. 用另一種觀點來看邊有標號的有根樹數量。每一步我們加上一條有向邊,考慮加邊加到現在的生成森林,這一步加上去的有向邊的起點可以是任何一個點,但是終點必須是某個連通塊的根,而且不能是同一個連通塊。也就是說,在第$i$輪有$N \times (N-i)$種選擇,因為除了自己以外的連通塊有$N-i$個。於是總方法數是$\prod\limits _ {i=1}^{N-1} N (N-i) = N^{N-1} (N-1)!$
  3. $X \times N \times (N-1)! = N^{N-1} (N-1)! \Rightarrow X = N^{N-2}$

同樣地,我們先假設本題的答案是$X$,並且令$S = \sum d _ i$

  1. 考慮某種連接零件的方式,並且把$N-1$個邊加上編號,這樣的方式總共有$X \times (N-1)!$種。
  2. 首先,先在每個零件選擇一個特殊孔,大致上是負責當作那個點和他的父節點連接的孔。在前$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)$種方法。
  3. 故 $X = \prod\limits d_i \prod\limits _ {i=0}^{N-3} (S - N - i)$

這題是我跑去找別人的解QQ
我看了好多解,好像都有用到Cayley定理甚至生成函數之類的QAQ好噁心
找了好久最後看到官方youtube的講解才聽懂

AC CODE

總結

這次有點可惜沒做出E QQ
然後看別人blog的時候驚訝他怎麼那麼厲害orz
希望某次有機會破台ARC

comments powered by Disqus