ARC 瞎做

范围：\(\text{ARC}[\ge104][\text{C|D|E|F}]\land\text{Difficulty}\ge1600\)。

ARC104

C

可以发现一段极小的合法区间必然是这样的一个形式：

\[[x,x+y],[x+1,x+y+1],\ldots,[x+y-1,x+2y-1].\]

然后你直接判区间合法 dp 一下就行了。细节有点多。

D

考虑 dp，令 \(dp_{i,j,k}\) 表示考虑了 \(1\sim i\) 的所有数字，一共选了 \(j\) 个，和为 \(k\) 的方案数。

直接做是 \(n^7\) 的过牛魔啊。。。

首先前缀和优化砍掉一个 \(n\)。然后你发现状态数就是这么多，必须优化状态数。

考虑求 \(x\) 的答案，不妨整体平移 \(x\)，那么就是 \(1-x\) 到 \(n-x\) 各 \(k\) 个，选出若干个和为 \(0\)。

那么设 \(dp_{i,j}\) 表示考虑了 \((1-x)\sim(i-x)\) 的所有数，和为 \(j\) 的方案数。那么求单个数的答案是 \(n^4\) 的，常数小也许能冲过去？

考虑正负分开算，设 \(dp_{i,j}\) 表示考虑 \(1\sim i\) 的所有数，和为 \(j\) 的方案数。

那么可以发现 \(x\) 的答案就是 \(\displaystyle(k+1)\sum_{i=0}^\infty dp_{x-1,i}\cdot dp_{n-x,i}\)。（就是正数总和等于负数绝对值总和）

那么时间复杂度为 \(\Theta(n^4)\)。

E

厉害题。看了题解才会。

考虑爆枚这 \(n\) 个数的大小关系（可能相等），然后算出它的 LIS 长度，那么转化为求方案数。

发现问题变成了：

给出 \(A\)，求满足 \(1\le a_i\le A_i\) 的严格上升序列 \(a\) 的数量。

不妨假设 \(A\) 不降，\(A_0=0\)。

设 \(dp_{i,j}\) 表示将 \(1\sim a_j\) 填在 \([1,A_i]\) 中的方案数。

那么有转移：

\[dp_{i+1,j+k}\gets \binom{A_{i+1}-A_i}k\cdot dp_{i,j}.\]

由于 \(k\) 很小直接 \(\Theta(k)\) 算组合数即可。

然后就做完了。时间是 \(\Theta(n^n\cdot\mathrm{poly}(n))\)，但是多几只 \(n\) 也随便冲。

F

不妨设 \(-1\) 的位置有一个无限高的，不影响。

你考虑 \(p_i=j\) 的限制就是 \(p_j>p_i\) 且【\(i<k<j\) 时 \(p_j\le p_i\)】。

然后你考虑把笛卡尔树建出来，那么就是左儿子小于等于它的，右儿子小于它的。

那么枚举根就变成两个区间的子问题了，dp 即可。（设 \(dp_{l,r,v}\) 表示 \([l,r]\) 内，值域为 \([1,v]\) 的方案数。）

注意到无论你怎么限制也只需要 \(n\) 的值域，所以状态数为 \(\Theta(n^3)\)，转移只需枚举根，所以时间复杂度为 \(\Theta(n^4)\)。

ARC105

C

首先这题很难把骆驼状压，只能 \(n!\) 爆枚。那么就不能再带一只 \(m\) 了。

假设确定了一个顺序。现在我们要求出前后两只骆驼的最小距离。

考虑 dp，设 \(dp_i\) 表示第一只和第 \(i\) 只骆驼的最小距离。

转移时，考虑 \(j\sim i\) 只骆驼的限制：

\[\forall p\text{ such that }v_p<\sum_{k=j}^iw_i,dp_i\ge dp_j+l_p\]

用人话说就是重量超了就必须隔得够远。

注意到「所有 \(v_p\) 小于某个值」的位置会产生限制，那么可以按 \(v\) 从小到大排序，那么每次就是取一段前缀的 \(l\) 的最大值，预处理即可。转移时直接二分出产生限制的那段前缀即可。

于是时间复杂度为 \(\Theta(n!n^2\log m+m\log m)\)。

D

显然根据 \(n\) 的奇偶性会有一个人（设为 X）死命让异或和非 \(0\)，反之亦然。

那么首先如果所有的 \(cnt\) 都是偶数，那么另一个人只要模仿 X 的操作就能让 X 必输。

反之，X 可以每次把石子数最多的那袋扔到石子数最多的盘子，那么最后那个盘子的石子数会大于总数的一半，从而使异或和非 \(0\) 而获胜。

时间复杂度 \(\Theta(n)\) 或 \(\Theta(n\log n)\)。

E

GameCoder。

考虑最后加不动边时的图，可以发现一定是 \(1\) 和 \(n\) 分别在两坨点组成的团里。它有多少条边呢？假设其中一坨有 \(i\) 个点：

\[\begin{aligned} &\frac{i(i-1)}2+\frac{(n-i)(n-i-1)}2\\ =&\frac{i^2-i+n^2-2in+i^2+i-n}2\\ =&i^2-in+\frac{n^2-n}2 \end{aligned}\]

可以发现，如果 \(n\) 是奇数，那么最后边数的奇偶性是固定的，胜负已分。

如果 \(n\) 是偶数，那么其中一个人就会死命让 \(i\) 变成偶数，另一个人死命让 \(i\) 变成奇数。

然后反正就是考虑一下镜像操作，结论就是如果先手死命抢偶数，那么当且仅当 \(1\) 和 \(n\) 所在连通块大小至少有一个是偶数时先手赢；如果先手死命抢奇数，那么当且仅当有一个是奇数时先手赢。

F

这不是我们的 ABC327G 吗。

首先你需要发现这个 good 的一坨定义说的是那个图是一个连通二分图。

设 \(U\) 为全集，\(f_S\) 表示由 \(S\) 的导出子图组成的染色二分图的数量。（这个咋求等下再说）

那么参考那个题的套路，设 \(h_S\) 为由 \(S\) 的导出子图组成的连通染色二分图的数量。

那么容斥一下可以得到：

\[h_S=f_S-\sum_{\substack{T\subset S\\\min\{S\}\in T}}h_T\cdot f_{S\backslash T}\]

而连通二分图只有两种染色方式，那么答案就是 \(\dfrac{h_U}2\)。

然后看怎么求 \(f_S\)。

直接暴力枚举染色方案，那么方案数就是 \(2^{e}\)，其中 \(e\) 是连接两个异色点的边数。

但是暴力做是 \(\Theta(3^nm)\) 的，过不去。

考虑优化，预处理出 \(cnt_{S,i}\) 表示连接 \(i\) 和 \(S\) 中任意一点的边数。

那么考虑递推求 \(f_S\)。设 \(res_T\) 表示 \(T\) 中点染黑，其它染白，的异色边数。

则有 \(res_\varnothing=0\)；设 \(T\ne\varnothing\)，那么令 \(v\in T\)，易得 \(res_T=res_{T\backslash\{v\}}-cnt_{T,v}+cnt_{S\backslash T,v}\)。

这样就做到了 \(\Theta(3^n+2^nm)\)。

ARC106

D

注意到 \((a+b)^c=\displaystyle\sum_{i=0}^c\binom cia^ib^{c-i}\)，令 \(s_i=\displaystyle\sum_{j=1}^na_j^i\)，那么就有

\[\begin{aligned} &\sum_{i=1}^n\sum_{j=i+1}^n(a_i+a_j)^x\\ =&\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=0}^x\binom xka_i^ka_j^{x-k}\\ =&\sum_{k=0}^x\binom xk\sum_{i=1}^na_i^k\sum_{j=i+1}^na_j^{x-k}\\ =&\sum_{k=0}^x\binom xk\cdot\frac12(s_ks_{x-k}-s_x) \end{aligned}\]

于是直接就 \(\Theta(nk+k^2)\) 做完了。

E

想了半天发现是唐题。

你考虑二分，然后直接上 Hall 定理就等价于对于任意一个员工集合 \(S\) 都有：\(S\) 中有员工来工作的天数 \(\ge k\cdot|S|\)。

容斥一下就是 \(S\) 里面一个也不来的天数小于某个值。

然后这个对于所有的 \(S\) 求可以高维前缀和做到 \(\Theta(n\cdot2^n)\)。

不难发现答案上界是 \(2nk\)，直接预处理每天的考勤情况即可。时间复杂度 \(\Theta(n^2k+nk\log(nk)+n2^n\log(nk))\)。

F

首先一个前置知识就是：给定度数序列 \(f\)，可以构成 \(\dfrac{(n-2)!}{\prod (f_i-1)!}\) 棵不同的树。（可以通过 Prüfer 序列证明）

那么如果钦定每个部分的度数 \(f\)，怎么统计不同的洞带来的贡献呢？

从每个部分随便排列 \(f_i\) 个洞，那么就可以将排列的第一个洞连到父亲，其它的依次连到儿子，可以证明这样是不重不漏的，所以方案数是 \(\dfrac{d_i!}{(d_i-f_i)!}\)。

那么就可以列出答案的式子：

\[\begin{aligned} &\sum_{f\text{ is valid}}\frac{(n-2)!\prod d_i!}{\prod(d_i-f_i)!(f_i-1)!}\\ =&(n-2)!\left(\prod_{i=1}^nd_i\right)\sum_{f\text{ is valid}}\prod_{i=1}^n\binom{d_i-1}{f_i-1}\ \end{aligned}\]

考虑算右边那坨东西。注意到 \(\sum f_i=2n-2\)，则 \(\sum(f_i-1)=n-2\)，考虑如下问题：

有 \(\sum(d_i-1)\) 个不同的物品，被分成了 \(n\) 组，第 \(i\) 组有 \(d_i-1\) 个。求从其中选出 \(n-2\) 个物品的方案数。

一方面，那一坨东西就相当于枚举每组选了多少个，再在每组里面选。

另一方面，直接选和分组再选没区别，所以它等于 \(\dbinom{\sum(d_i-1)}{n-2}\)。

所以答案为：

\[(n-2)!\left(\prod_{i=1}^nd_i\right)\binom{\sum(d_i-1)}{n-2}\]

时间复杂度 \(\Theta(n)\)。

ARC107

D

这个 dp 的思路很妙啊。

设 \(dp_{n,k}\) 表示对应的答案，则 \(n\ge k\)（否则答案显然为 \(0\)）。

我们讨论：

• 如果这里面有一个 \(1\)，那么就是 \(dp_{n-1,k-1}\)；
• 否则不妨把所有元素乘 \(2\)，那么就是 \(dp_{n,2k}\)。

然后就做完了。\(\Theta(n^2)\)。

E

纯结论题啊。。。

Lemma：对于任意的 \(4\le i,j<n\)，有 \(a_{i,j}=a_{i+1,j+1}\)。

Proof：

你发现只要某一行 \(>1\) 列的位置出了个 \(0\)，后面 \(2\) 列起就一定满足条件了。

然后你发现第 \(3\) 行起两个 \(0\) 就最多隔 \(2\) 个位置……

然后就感性理解……

你也可以写个暴力验证一下 \(5\times5\) 的网格……

然后你爆算前四行前四列就 \(\Theta(n)\) 了……

F

抽象网络流。

绝对值搁在那很难受，考虑换个说法：把它们赋一个（相同的）\(1\) 或 \(-1\) 的权值，和的最大值。

这样就舒服多了：最大值就是很能流的样子；连通块的和，其实就是赋的权值全一样；进一步地，就是相邻的两个结点权值必须一样。

那么此时每个结点有三种状态：赋 \(1\)，赋 \(-1\)，被删掉。

考虑最小割，总价值减去最小要移除的贡献：你对一个结点建两个点 \(X,Y\)，连一条边 \(X\to Y\)，然后设 \(Y\) 在 \(S\) 集代表赋 \(1\)，\(X\) 在 \(T\) 集表示赋 \(-1\)，否则表示删掉。

然后你随便处理一下限制就完了……

ARC108

D

不妨设 \(c_\texttt{ab}=\texttt a\)，则第一步只能是 \(\texttt{aab}\)。

此时如果 \(c_\texttt{aa}=\texttt a\)，不难发现只能生成 \(\texttt{aaa}\ldots\texttt{ab}\)，答案为 \(1\)。

否则还可以生成 \(\texttt{abab}\)，此时讨论：

• 如果 \(c_\texttt{ba}=\texttt a\)，则可得最终串中只需不存在相邻的两个 \(\texttt b\)，答案是斐波那契数列。
• 如果 \(c_\texttt{ba}=\texttt b\)，则最终串只需有前缀 \(\texttt a\) 和后缀 \(\texttt{ab}\)，答案为 \(2\) 的幂。

（以上结论读者自证不难。）

时间复杂度可以做到 \(\Theta(\log n)\)。

E

容易发现选出一个位置后左右独立，所以设 \(dp_{l,r}\) 为 \(l-1\) 和 \(r+1\) 都已选中，\([l,r]\) 内都还未选中时，\([l,r]\) 内的期望贡献。

令设 \(S_{l,r}=\{p\in \mathbb N\mid l\le p\le r,a_{l-1}<a_p<a_{r+1}\}\)，即区间内合法的凳子的集合。

则容易列出转移方程：

\[dp_{l,r}=\begin{cases}0,&S_{l,r}=\varnothing\\\displaystyle\frac1{|S_{l,r}|}\sum_{i\in S_{l,r}}1+dp_{l,i-1}+dp_{i+1,r},&S_{l,r}\ne\varnothing\end{cases}\]

对于每一项在值域上树状数组优化即可做到 \(\Theta(n^2\log n)\)。

F

考虑转换成对于每个 \(x\) 计算 \(\mathrm{niceness}\ge x\) 的方案数。

考虑充要条件：上式不成立当且仅当距离 \(\ge x\) 的点对全部异色。

如果直径长度 \(<x\) 显然不可能成立。

如果有一个点到直径两端的距离都 \(\ge x\)，那么直径长度也 \(\ge x\)，显然必定成立。

否则一个点最多和一个直径端点距离 \(\ge x\)。考虑距离 \(\ge x\) 的点对连一条边，那么不成立相当于这个图被二分图染色。

这个图的形状显然是直径两端各挂了一坨点，加上一坨孤立点。求孤立点数量也是好做的，直接 bfs 一下算一下到直径端点最短距离就行了。

ARC109

D

人类智慧 + 打表大法 题，无法理解，咕。

E

结论很神仙：

如果两边颜色一样最后肯定全是那种，否则看两个最靠边的连通块哪个离初始点远，远的种颜色就只有那一段。

证明略。

然后你考虑两边差的是哪一部分，注意到大多数都会被对称掉，那么剩下的就是距离相等的情况，这种情况必然是黑棋得到中间的。

然后再进行一堆 dirty 的推式子，你会得到一个对于钦定的起点的式子。

然后你发现这玩意每一位都是前一位加了一项，直接递推即可。\(\Theta(n)\)。

F

没做，咕。