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\)，那么就可以考虑先把出现次数为奇数次的位去掉。