【Atcoder】AGC005 C-F簡要題解

C.Tree Restoring

首先找到直徑 L L L，設 x = ⌈ L 2 ⌉ x=\lceil \dfrac L2\rceil x=⌈2L​⌉。

( x , L ] (x,L] (x,L]的數都至少有2個， &lt; x &lt;x <x的不存在。

L L L為奇數時， x x x有且僅有2個；為偶數時， x x x有且僅有1個。

D.~K Perm Counting

考慮容斥，令 g i g_i gi​表示至少有 i i i個點不合法的方案數。

a n s = ∑ i = 0 n ( − 1 ) i g i ( n − i ) ! ans=\sum\limits_{i=0}^n (-1)^ig_i(n-i)! ans=i=0∑n​(−1)igi​(n−i)!。

關鍵在于如何求 g i g_i gi​(沒想出來，zz了)，由于每個位置最多隻有2個權值不合法，考慮構造二分圖，左邊點表示位置，右邊點表示權值。

可以發現圖上的邊是一條條鍊(且這 2 n 2n 2n個點都在且僅在一條鍊上)。

考慮把這些鍊首尾相連， d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1]表示處理到第 i i i個點，已經選了 j j j條不和法的邊， i i i點是否與 i − 1 i-1 i−1相連的方案數。

d p [ i ] [ j ] [ 0 ] = d p [ i − 1 ] [ j ] [ 0 ] + d p [ i − 1 ] [ j ] [ 1 ] dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1] dp[i][j][0]=dp[i−1][j][0]+dp[i−1][j][1]

若目前點不是某條鍊的結尾， d p [ i ] [ j ] [ 1 ] = d p [ i − 1 ] [ j − 1 ] [ 0 ] dp[i][j][1]=dp[i-1][j-1][0] dp[i][j][1]=dp[i−1][j−1][0]

設總鍊長為 m m m，則 g [ i ] = f [ m ] [ i ] [ 0 ] + f [ m ] [ i ] [ 1 ] g[i]=f[m][i][0]+f[m][i][1] g[i]=f[m][i][0]+f[m][i][1]

E.Sugigma: The Showdown

若紅樹上某一條邊的兩個端點在藍樹上距離 &gt; 2 &gt;2 >2，則若先手到達了這兩個端點之一，就必勝。

建出以後手為根的藍樹，删去紅樹上所有滿足上面條件的邊，并對這些端點打上标記，建出紅樹。

此時，由于紅樹上任意邊的兩個端點在藍樹上距離 ≤ 2 \leq 2 ≤2，是以若後手點在藍樹中所有先手點到标記點的路徑上，則後手必勝。此時讓先手到子樹最深點呆着即可。

F.Many Easy Problems

容斥考慮一個點對所有 a n s k ans_k ansk​的貢獻：

( n k ) − ∑ ( n a i ) \dbinom{n}{k}-\sum\dbinom{n}{a_i} (kn​)−∑(ai​n​)

a i a_i ai​表示以 i i i為根時 i i i的每個兒子結點的子樹大小。

發現對于 a n s k ans_k ansk​， ( n k ) \dbinom{n}{k} (kn​)被算了 n n n次，每條邊兩端的子樹 ( s z k ) \dbinom{sz}{k} (ksz​)被算了一次。

設 b n = n , b i = 大 小 為 i 的 子 樹 個 數 ( i ≠ n ) b_n=n,b_i=大小為i的子樹個數(i\neq n) bn​=n,bi​=大小為i的子樹個數(i̸​=n)

a n s k = ∑ i = k n b i ( i k ) ans_k=\sum\limits_{i=k}^n b_i\dbinom{i}{k} ansk​=i=k∑n​bi​(ki​)

  = 1 k ! ∑ i = k n b i i ! 1 ( i − k ) ! \qquad\ =\frac{1}{k!}\sum\limits_{i=k}^n b_ii!\dfrac{1}{(i-k)!}  =k!1​i=k∑n​bi​i!(i−k)!1​

設 A ( x ) = ∑ b n − i ( n − i ) ! x i , B ( x ) = 1 i ! x i A(x)=\sum b_{n-i}(n-i)!x^i,B(x)=\frac{1}{i!}x^i A(x)=∑bn−i​(n−i)!xi,B(x)=i!1​xi

C = A ∗ B → a n s k = n − k k ! C=A*B\to ans_k=\dfrac{{n-k}}{k!} C=A∗B→ansk​=k!n−k​

一遍NTT即可