Atcoder 做題記錄

\(\bullet\) \(\texttt{ ARC099F Eating Symbols Hard}\)

用哈希值 \(h_i\) 表示執行完 \(S_{(0,i]}\) 的操作後的序列 \(A\) ：

\[h_i = \sum\limits_{j=-\infty}^{\infty}A_j{Base}^j\pmod {M}

\]

對于四個操作：

\[+ \longrightarrow h = h+{Base}^p

\[- \longrightarrow h = h - {Base}^p

\[> \longrightarrow p = p+1

\[< \longrightarrow p = p-1

記 \(p_i\) 為執行完 \(S_{(0,i]}\) 的操作後 \(P\) 的位置，

考慮隻執行 \((l,r]\) 的操作後 \(A\) 的哈希值：

\[h_{(l,r]} = \dfrac {(h_r-h_l)}{{Base}^{p_l}}

若合法，則有： \(\dfrac {(h_r-h_l)}{{Base}^{p_l}} = h_n\)

移項得到 \(h_r = h_l + h_n{Base}^{p_l}\)

枚舉 \(l\) 數有多少 \(r\) 即可，時間複雜度 \(O(n \log n)\)。

\(\texttt{Code}\)

\(\bullet\) \(\texttt{ ARC102E Stop. Otherwise...}\)

考慮 \(OGF\) 。

對于 \(ans_i\)，有三種點數：

• 任意選的，記數量為 \(a\)，\(OGF\) 為 \(\dfrac 1 {1-x}\)；
• 成對且和為 \(i\) 的數，記數量 \(b\)，\(OGF\) 為 \(\dfrac {1 + x} {1-x}\)；
• \(i/2\)，隻能取一個，\(OGF\) 為 \(1 + x\)。

則 \(ans_i = \sum\limits_{j=0}^{\infty}[x^j]\dfrac {(1+x)^{b}} {(1-x)^{a+b}}(i\&1 ?1:(1+x))\)

将其簡化，變成求 \([x^n]\dfrac {(1+x)^a}{(1-x)^b}\)，推一下：

\[\begin{aligned}[x^n]\dfrac {(1+x)^a}{(1-x)^b}&=[x^n](1+x)^a(1-x)^{-b}\\&=\sum\limits_{i=0}^n[x^i](1+x)^a[x^{n-i}](1-x)^{-b}\\&=\sum\limits_{i=0}^n\dbinom{a}{i}\dbinom{b+(n-i)-1}{n-i}\end{aligned}

直接計算，時間複雜度 \(O(nk)\) 。

\(\bullet\) \(\texttt{ AGC013E Placing Squares}\)

先不考慮 \(m\) 個點的限制，記 \(dp_i\) 表示覆寫了前 \(i\) 塊的總和，則有：

\[dp_{i+1}=\sum\limits_{j=0}^{i}dp_j(i+1-j)^2

直接做是 \(n^2\) 的。

考慮把 \((i+1-j)^2\) 展開，得到：

\[dp_{i+1}=\sum\limits_{j=0}^idp_j(i-j)^2 + 2\sum\limits_{j=0}^idp_j(i-j)+\sum\limits_{j=0}^idp_j

記 \(A_i = \sum\limits_{j=0}^{i-1}dp_j(i-j)^2,B_i = \sum\limits_{j=0}^{i-1}dp_j(i-j),C_i = \sum\limits_{j=0}^{i-1}dp_j\)，則 \(dp_{i+1} = A_{i+1} + B_{i+1} + C_{i+1}\)。

觀察到 \(n\) 很大，但是 \(m \le 10^5\)，實際上可以分成 \(O(m)\) 段沒有限制的區間，使用前面的 \(dp\) 轉移，考慮矩陣快速幂：

假設已經知道 \(\begin{bmatrix}A_i & B_i &C_i\end{bmatrix}\)，求 \(\begin{bmatrix}A_{i+1}&B_{i+1}&C_{i+1}\end{bmatrix}\)。

• \(dp_{i} = A_i\)
• \(A_{i+1} = A_i + 2B_i + C_i + dp_i = 2A_i + 2B_i + C_i\)
• \(B_{i+1} = B_i + C_i + dp_i = A_i + B_i + C_i\)
• \(C_{i+1} = C_i + dp_i = A_i + C_i\)

則轉移矩陣為：

\[\begin{bmatrix}2&1&1 \\2&1&0\\1&1&1\end{bmatrix}

若 \(i\) 點為星星，則轉移矩陣為：

\[\begin{bmatrix}1&0&0\\2&1&0\\1&1&1\end{bmatrix}

\(\bullet\) \(\texttt{ ARC066E Addition and Subtraction Hard}\)

性質題：

• 括号隻加在減号後面
• 加了括号後，括号裡面的數前面如果有減号，那麼一定可以對答案貢獻正數

于是直接枚舉最外層的左括号，取最大值即可。

\(\bullet\) \(\texttt{ ARC060F Best Representation}\)

首先考慮整個串是否有循環節，這個可以使用 \(kmp\) 解決。

若沒有循環節，則答案一定為 \(1,1\)；

否則，分類考慮：

• 循環節是 \(1\)：答案一定為 \(n,1\)；
• 循環節 \(>1\)：可以發現，\(s_{1..n-1}\) 和 \(s_n\) 可以構成一組合法的解，則最優方案一定是分成兩段，于是可以枚舉斷點數一下有多少合法方案， \(\bmod 1e9+7\) 是唬人的。。

\(\bullet\) \(\texttt{ AGC009C Division into Two}\)

\(\color{black}l\color{red}bylby\) ：預測性

dp

記 \(f(i,0/1)\) 表示第

i

個數放入集合

0/1

，第

i+1

1/0

的方案數。

可以得到 \(O(n^2)\) 的暴力，然後發現轉移是一段區間，維護一下可以做到 \(O(n)\) 。

\(\bullet\) \(\texttt{ ABC213G Connectivity 2}\)

狀壓

dp

小

trick

。

記

cnt(S)

為集合

S

内元素間的總邊數，

f(S)

為使得集合

S

中的所有點聯通的選邊方案數，則有：

\[\large f(S) = 2^{cnt(S)} - \sum\limits_{T\subsetneqq S} f(T) 2^{cnt(S/T)}

但是這樣會算重，可以考慮欽定一個點

u

沒有和

S

聯通，轉移變成：

\[\large f(S) = 2^{cnt(S)} - \sum\limits_{T\subsetneqq S,u\in T}f(T)2^{cnt(S/T)}

于是就做完了。

\(\bullet\) \(\texttt{ ARC066D Xor Sum}\)

假設已有一對 \(a,b \Longrightarrow u,v\) 合法：

• 若将 \(a,b\) 各自左移一位，可以得到 \(2a,2b \Longrightarrow 2u, 2v\)。
• 若左移後 \(a,b\) 其中一方加 \(1\)，得到 \(2a+1,2b \Longrightarrow 2u+1,2v+1\)
• 若左移後 \(a,b\) 分别都加 \(1\)，得到 \(2a+1,2b+1 \Longrightarrow 2u,2v+2\)

記 \(f(n)\) 為 \(u,v,a,b \le n\) 時的答案，則：

• 若 \(n\) 為奇數，則 \(f(n) = f(n/2) + f(n/2) + f(n/2-1)=2f(n/2)+f(n/2-1)\)
• 若 \(n\) 為偶數，則 \(f(n) = f(n/2) + f(n/2-1) + f(n/2-1) = f(n/2) + 2f(n/2-1)\)

時間複雜度 \(O(\log n)\)。

\(\bullet\) \(\texttt{ ABC217G Groups}\)

記 \(f_n\) 表示恰好被分成 \(n\) 個不區分的非空集合的方案數，\(g_n\) 表示被分成 \(n\) 個區分集合的方案數。

則有：

\[\large g_n=\sum_{i = 1}^n\dbinom n if_i i!=\prod_{i=0}^{m-1}\dbinom n {cnt_i}cnt_i!

二項式反演得到：

\[\large n!f_n = \sum_{i=1}^n(-1)^{n-i}\dbinom n i g_i

直接計算即可做到 \(O(n^2)\) 。

\(\bullet\) \(\texttt{ ABC141F Xor Sum 3}\)

可以發現，若二進制下第 \(i\) 位出現了奇數次，無論怎麼劃分都會答案貢獻 \(2^i\)，那麼就可以考慮先把出現次數為奇數次的位去掉。