这场我感觉题很不错的QwQ

C DFS Game

考虑先手到达一个根。然后先手必然会取走这个根上的硬币。然后后手会选择一个儿子向下，然后又变成先手到达一个根的问题。所以感觉上需要考虑 $dp$ 。但是事实上从这个子树回溯回来之后，不一定开始的先手仍然作为先手。所以可以考虑 $dp[u]$ 表示先手到达 $u$ 后可以获得的价值减去后手可以获得的价值的最大值。设最终先手获得硬币数是 $a$ ，后手是 $b$ ，那么 $a+b=n$ ，所以只需要最大化 $a-b$ 即可。

考虑如何转移。不难发现当我们经历完一个子树后是否切换先后手是肯定的，取决于子树的大小，因为每条边都会被经历两次不影响，所以如果大小是奇数则会切换，否则不会。

我们考虑把所有子树按照是否切换分开。那么后手在开始选择子树的时候，一定会先选那些不会切换的，且后手更优的子树，即 $dp[v] < 0$ 的 $v$ ，因为这些东西选了后是一定更优的。这些树选完后一定会选择 $dp$ 值最小的切换的子树。因为选择先手赚的子树是稳亏的。然后选完最小后，曾经的先手就变成了后手，肯定也会选 $dp$ 值最小的切换的子树，只是对答案的贡献变成了 $-dp[v]$ 。于是就变成了一个 $+-+-$ 交替进行的局面。在选择完所有切换的子树后，谁选择剩下的稳亏的子树就确定下来了。

复杂度 $O(n)$ 。

D Skate

考虑边界列的东西显然是可以被任何点达到的。而如果边界上某一列有 # ，那么这一列就一定全部可以被任何点达到。

再想想会发现本质上是，一个可以被任何点达到的点的同一列、同一行都可以被任何点达到。

所以如果只是判断当前图是否合法，我们可以做一个 bfs 来看看是否所有点都能被达到，即是否所有行或者所有列都合法了。显然，一张图合法当且仅当所有行合法或所有列合法。

但是原题是让我们加入一些 # 。显然，一定有一个最优决策可以把 # 添加到边界上。因为加入一个 # 后显然最多只能让一列或一行合法，不然意味着这个 # 无法被达到。所以我们可以直接加到这一行或列的边界上。

然后就自然有了一个想法，我们给每一行每一列分别建一个点。然后按行列之间的合法关系连边，即对于一个 # 给这一行这一列连。然后我们把第一行，最后一行，第一列，最后一列钦定成合法的。

然后考虑就只是需要看看每个行联通快当前是否合法，如果不合法就把它变成合法同时给行的答案 +1 ，列同样做，取最小值即可。

E Cigar Box

好题。

首先会发现，知道最后都没有被操作过的数一定在最终序列上形成一段区间。

我们设 $dp[i][k]$ 表示到现在为止操作过 $i$ 次，一共有 $k$ 个数已经被操作过了，需要注意的是，这里的 $dp$ 中已经钦定好了这 $k$ 个数分别是谁。为了方便，我们给除开区间内的数重编号一下成为 $1 \sim k$ 。

具体来说，我们做的这个 $dp$ 相当于在统计有多少个长度为 $m$ 的序列，满足其中出现的一定是 $-1\sim -k , 1 \sim k$ 里面的数，正负表示向左或右。而每个数的最后一次操作被认为是没有被确定方向的，因为在状态中并不知道最后有多少个数被操作到了左边，多少个到了右边。在枚举了最终序列中没有被操作的区间后，假设最后左边有 $l$ 个右边有 $r$ 个数是被操作过的，答案就是

$$dp[m][l + r] \times \binom{l+r}{l}$$

相当于是我们给没有确定状态的位置都确定了方向。而且在确定方向后，它们的编号也会被唯一确定下来，因为你是知道最后左边、右边 $l,r$ 个数分别是多少的。

但是直接算这个 $dp$ 会比较毒瘤，因为不太好确定一个数最后一次被操作的时刻。但是会发现如果倒着考虑这个问题就变得非常轻松。于是转移分为两种，要么是选择一个到现在已经被操作过的数再操作一次（具有方向），要么放一个新数，作为它的最后一次操作，因此没有方向。而因为前面说到的，新数的编号在乘上组合数后就被唯一确定了。

因此转移：

cpp

dp[i][j] = ( dp[i][j] + dp[i - 1][j] * 2ll * j ) % P;
dp[i][j + 1] = ( dp[i][j + 1] + dp[i - 1][j] ) % P;

统计答案就是枚举一段区间作为没有被操作过的，给答案加上这种情况的贡献即可。复杂度 $O(n^2)$ 。

F Die Siedler

神仙题。

考虑一个非常重要的事：实际上的状态数其实不多，只有 $\prod 2^i i!$ 这么多种。如果取 $n = 16$ ，也只有 $10^{18}$ 级别。而且这个转化很有意思，类似于一个每一位进制不同的数，而这个数是可以存下的。如果我们设

$$H(s) = \sum_{i=0}^{n-1} 2^i i! s_i$$

那么除了开头转化成结尾的情况，两个状态 $s$ 的 $H$ 相同就意味着两个状态等价。

考虑开头转化成结尾，可以类似循环卷积的东西给它模一个 $M=2^nn!-1$ 。然后相当于是每当到达 $2^n n!$ ，即出现 $n$ 个 $2^{n-1}(n-1)!$ 就转化一个 $1$ 。这样就可以几乎完美地表示两个状态等价了。但是事实上，这样会导致分不清 $0$ 状态和全满状态，因为这两个状态都是 $0$ ，但是这题非常良心地保证了初始状态非 $0$ ，不难发现初始状态不是 $0$ 就不可能回到 $0$ 状态，所以如果出现 $H(s) = 0$ 一定表示 $s$ 是满状态。

同时，这么定义 $H$ 还有一个好处，我们可以方便地求出对于一个值 $h = H(s)$ 达到它需要的最少个数。具体来说就是从高位到低位贪心放，类似进制转换。

我们考虑对所有卡包都求出 $H$ 。那么选择一个卡包就是加上它的 $H$ 。也就是说我们可以进行的操作就是加上这些卡包与模数的一个线性组合。由裴蜀定理，这些卡包能凑出的最小的正数是

$$g = \gcd\{M,h_1,h_2,\dots ,h_m\}$$

也就是说我们可以看成每次只能给当前值加上 $g$ 。

于是就变成了求 $\min f(s+kg)$ ，其中 $f$ 表示一个状态需要最少的个数。

然后就到了最神仙的一步，对这 $16$ 种 $M$ 进行一次打表。可以发现对于所有 $M$ ，它的约数要么不到 $B = 2\times 10^6$ ，要么超过了 $\frac{M}{B}$ 。

由于 $g$ 是一个 $M$ 的约数，如果 $g > \frac{M}{B}$ ，那么显然可以每次暴力给初始状态 $s$ 加上 $g$ ，然后暴力判断。复杂度是 $O(Bn)$ 。

如果 $g < 2\times 10^6$ ，考虑设 $dp[x]$ 表示在模 $g$ 意义下到达同余于 $x$ 这个状态所需要的最少数字个数。由于边权只有 $1$ （一次只能选择一个数），所以可以 bfs 求解，复杂度 $O(Bn)$ 。

于是这个题复杂度 $O(Bn)$ 。