UOJ NOI Round #2 题解

先来个小问题？

MysteryMan 是谁呢？

关于这点，我只能告诉你无可奉告，你们不高兴也不行。

好吧其实是一个2009年左右的不愿透露姓名的OI选手……

Day1

UOJ拯救计划

from MysteryMan，题解 by ydc

大家好，这是 MysteryMan 出的题，题解由失踪多年的ydc来写。

这题说白了就是求解图染色方案数，由于图染色问题是NPC的，因此只要你输出答案模6的值。

对于前$30\%$的数据，我们直接爆搜即可，$O(k^n)$。

对于$4,5$两个测试点，由于$k=1$，我们发现只有当$m=0$时有解（且解为$1$）。当然爆搜也是可以的。

对于$6$号测试点，由于是一棵树，我们可以用组合计数的方法得知答案为$k*(k-1)^{n-1}$

对于满分做法，我们首先可以推导得知答案为$\sum\limits_{i=1}^k A(k,i) \times $恰好用$i$个颜色染色的方案数，A为排列数，然后由于答案要模$6$，因此当$i \ge 3$时，对答案贡献为$6|A(k,i)$。

所以我们唯一要做的就是考虑$i=1,i=2$，当$i=1$的话，只有当$m=0$的时候才有解，所以问题就是只考虑$i=2$了。

我们知道，对于一个联通的二分图，确定了一个点后，其余点的颜色就都确定了。因此，我们判断整张图是否是二分图。如果不是二分图，直接输出$0$，否则统计联通块个数，输出2的联通块个数次方即可。

最后有一个小细节即$m=0$，因为当$m=0$的时候，恰好用两个颜色染色的方案数就不是2的联通块个数次方，而要减去全黑和全白。

这题还有另一个思考的思路，即色数多项式——一张$n$个点图的染色方案是关于$k$的$n$次多项式，记作$f(k)$。我们要想知道$f(k)$模6的值，只要知道$f(k)$模$2,3$的值即可。要想知道$f(k)$模$2,3$的值，只要知道$f(0),f(1),f(2)$模$2,3$的值即可。然后就能得到一个殊途同归的算法。

排兵布阵

from MysteryMan，题解 by jiry_2

收题的时候我感觉这题应该是 T3 的，但是当了几个月甩手掌柜之后发现这题被放到了 T2..感觉组题的人有点石乐志。

C_SUNSHINE：“行吧我石乐志……”

算法一

直接 $O(n^2)$ 暴力，可以通过第一个数据集。

算法二

没有移动操作，那么可以用处理矩形加，询问矩形信息的数据结构 kd-tree 来做。

时间复杂度 $O(n \sqrt n)$，可以通过第二个数据集。

当然肯定有其他复杂度更低的方法。

算法三

因为这是一道对着 idea 出的题，所以不排除有简单的算法或者复杂度更低的算法，但是这题的 idea 本身还是很妙的。

考虑这么一个数据结构：我们对平面里的每一行统计这一行的点数 $nx_i$，每一列统计这一列的点数 $ny_i$。对于一个点 $(x,y)$，如果 $nx_x \geq ny_y$，那么它就作为 $y$ 列的关键点，否则就作为 $x$ 行的关键点。

不难发现每一行每一列的关键点个数都是严格 $O(\sqrt n)$ 的。

于是思路就是每一个操作，都是关键点上暴力，非关键点打标记，同时对每一行每一列维护非关键点的权值最大值。这样每一次操作都是严格 $O(\sqrt n)$ 的。

只要利用好每一个点要么是行关键点，要么是列关键点，那么每一个操作都可以顺其自然的暴力了。

思路虽然简单但是细节还是比较多的：

维护权值

这个问题的核心在于把横纵的修改和询问联系起来。在刚才那个结构中，可以定义一个行关键点 $(x,y)$ 的权值为它的点权加上列 $y$ 上的非关键点加标记。

这样在行操作的时候，我们把每一个行关键点的点权修改一下，同时更新这个关键点所在列的非关键点最大值。列操作类似。

关于合并

关于合并一个简单的想法是，直接把关键点集合并起来，然后把非关键点最大值取个 $\max$，但是实际上没有那么简单。

首先是标记，在合并两个有标记的行的时候，因为标记是不能下传的（下传要遍历每一个非关键点并修改，复杂度爆炸了）。所以标程的做法是对行和列分别维护一个并查集，同时用类似同态加边判断是否是二分图的方法，在并查集的每一条边上维护儿子和父亲的标记差。

这样对于一个原来坐标是 $(x,y)$ 的点，我们要看它列上的标记，只要在列并查集里求它到根的边权和就可以了。

接着，因为在合并了两行之后，行的点数变多了，所以一些行关键点会变成列关键点。这个时候我们要遍历所有行关键点，然后看关键点是否会跑到另一边去。因为一次合并之后关键点也是 $O(\sqrt n)$ 的，所以这一步也可以暴力。但是要注意的是行关键点变成列关键点后，这个点的点权要根据行列的标记修改一下以满足我们刚才的定义。

关于去重

行列的关键点个数是 $O(\sqrt n)$ 的分析建立在没有重点的基础上，但是合并的过程中会出现重点，这个时候我们需要对关键点去重。

去重的过程相当于把所有相同位置的关键点变成一个点，且权值为这个位置所有关键点的最大值。

如果每一次合并都去重的话，去重的复杂度在瓶颈上，必须要写 hash 之类的方法，常数较大。

实际上可以设一个阈值 $S$，例如 $\frac{3}{2}\sqrt n$，然后在每一次我们要暴力扫关键点集合的时候，如果我们发现关键点数量超过了 $S$，那么就进行一次去重。

因为每一次去重都至少删掉了 $O(\sqrt n)$ 个点，而总点数只有 $n$，所以去重的复杂度不在瓶颈上，可以用 map 暴力。

综上，这个算法的时间复杂度是 $O(n \sqrt n)$ 的，并查集、去重的时间复杂度都不是瓶颈。可以通过后两个数据集。

第三个数据集的用意是避免掉合并操作时标记合并的一些细节。当然可能存在着一些针对性的算法。

个人感觉这题的 idea 还是挺不错的，但是好的 idea 到好的题目的过程还是有点难.. 之前思考熊那题就是这么翻车的。这题虽然有 $6$ 个操作但是因为横竖是对应的如果写的好的话应该可以只写 $3$ 个操作，或者竖的部分可以从横的部分贴过来改一下。因此代码量虽然略大但是应该还是在 OI 比赛可接受范围内，当个 T3 挺合适的。

（不过 UNR 传统是 T2 最难？）

C_SUNSHINE：“Exactly!”

黎明前的巧克力

from sevenkplus，题解 by C_SUNSHINE

题解很啰嗦，觉得想的差不多的可以直接看算法七。

算法一

我们可以 $3^n$ 直接枚举每个巧克力是在 Evan 的集合 $A$ 里还是 Lyra 的集合 $B$ 里，并判断异或值是否相等，时间复杂度$O(3^n)$，期望得分 5 分。

算法二

我们重新考虑算法一，我们可以先枚举一个巧克力是否在 $A + B$ 里，再考虑是再谁的集合里，由于两个集合的异或值相等，$A + B$ 的异或值一定为 $0$，接着观察可以发现， Evan 可以选择 $A + B$的任何一个子集作为 $A$，Lyra 只要选择其补集即可，所以我们只要对于所有异或和为 $0$ 的集合 $S$，把 $2^{|S|}$ 加到答案里去就好了，最后别忘了 $-1$ 去掉 $S$ 为空集的情况。

如果我们枚举所有可能的 $S$ 集合，我们的算法复杂度就是$O(2^n)$，期望得分 15 分。

算法三

当$a_i$的值域不大的时候，显然这个东西我们是可以DP的，定义一个集合 $S$ 的权值为 $2^{|S|}$。我们可以用 $f_{i,j}$ 表示，前 $i$ 个数，异或和为 $j$ 集合的权值和。那么转移时枚举当前数选不选：

$f_{i-1,j} \rightarrow f_{i,j}$

$f_{i-1,j}\times 2 \rightarrow f_{i,j~xor~a_i}$

用 $m$ 表示最小的 $k$ 满足所有 $a_i$ 都小于 $2^k$，这个做法的时间复杂度是$O(n2^m)$的，结合前面的算法，期望得分 30 分。

算法四

注意到有部分数据不同的数字种类数不算多，我们可以发现一个数字选奇数个对异或和的贡献都是一样的，于是我们用组合数预处理每个数选奇数个/偶数个的权值和，再按数字DP，每次枚举当前数字是选择奇数个还是偶数个进行转移即可，转移方法类似算法三。

假设有 $D$ 个不同的数字，时间复杂度是 $O(D2^m)$，期望得分 40 分。

算法五

继续观察算法三，可以发现每次转移相当于是原数组和当前数组 $F_{a_i}$ 做了一个 $XOR$ 卷积，当前数组 $F_{a_i}$ 满足 $F_{a_i}(0)=1$，$F_{a_i}(a_i)=2$，其他位置上都是 $0$，那我们考虑使用快速沃尔什变换(FWT)来优化这个位运算卷积。

对每一个数 $a_i$ ，都求出 $FWT(F_{a_i})$，然后把这些变换之后的数组乘起来，在逆变换回去得到 $G$，最后输出 $G(0)$ 即可。

这样，你就可以获得…… 0 分了，可以发现这算法的复杂度是 $O(nm2^m)$ 的，会全部TLE。

算法六

作为新时代的OI少年，我们一定要把这个FWT优化到极致，继续观察这个FWT的性质，可以发现 $F_{a_i}$ 只有两个位置上有值，那不妨把 FWT 的结果打印出来观察一下——

可以发现每个位置都是 $-1$ 或者 $3$。

由于FWT是线性变换，即$FWT(F_1+F_2) = FWT(F_1)+FWT(F_2)$，所以若第 $a_i$ 位上的 $2$ 对 $x$ 位置贡献了一个 $+2$ 则第 $x$ 位上是 $3$，反之贡献了 $-2$ 导致 $x$ 位置上是 $-1$。

接着观察可以发现，当 $x~and~a_i$ 的二进制中有偶数个 $1$ 时，贡献为 $+2$，否则贡献为 $-2$。

为什么呢？

不妨采用高维FFT理解FWT来证明一下，我们把数字 $x$ 二进制下的第 $k$ 位用 $x_k$ 表示，则FWT可以写成：

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

由于 $01$ 变量的乘法可以看成 $and$，令 $bitcount(x)$ 表示 $x$ 二进制中 $1$ 的数目，则：

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} F(k) (-1)^{bitcount(n_j~and~k_j)}$$

那么这个式子怎么算呢？

不妨考虑枚举 $t=n_j~and~k_j$，在枚举 $s$ 是 $t$ 的超集即$s~and~t = t$，则能收到 $s$ 的贡献的位置 $x$ 满足的条件是，$t$ 的超集集合中，除了 $t$ 为 $1$ 的那几位之外，与 $s$ 没有交集的 $x$。只考虑 $t$ 之外的位，可以发现 $s$ 的贡献其实是针对一个子集的，所以我们只要对子集打上标记，最后补集转化后做子集和变换就可求得贡献和了。

现在我们会求所有元素的贡献和了，可我们要的不是贡献和啊，我们要的是贡献积，这怎么办呢？

假设对于某一个贡献和为 $s$ 位置，$x$ 个数贡献了 $-1$，那么就有 $n-x$ 个数贡献了 $3$，于是列出方程 $3(n-x)-x=s$，可以解得 $x=\frac{3n-s}{4}$。

解出 $x$ 之后，贡献积就是 $(-1)^x \times 3^{n-x}$了，用快速幂计算即可，之后逆FWT回来输出 $G(0)$ 就可以了。

由于要枚举集合和超集，还要做子集和变换，时间复杂度是 $O(n+m3^m)$，结合前面算法期望得分 65 分。

算法七

之前提到过，对于贡献和为 $s$ 位置，设$x$ 个数贡献了 $-1$，列出方程 $3(n-x)-x=s$，可以解得 $x=\frac{3n-s}{4}$，接着贡献积是 $(-1)^x \times 3^{n-x}$了，用快速幂计算即可。

那么观察算法六我们的推导过程，可以发现我们对FWT做了细致的解析，然而既然我们知道他是FWT，其实完全可以不做这个解析，直接用FWT计算贡献和即可。

简单来说我们直接把每一个数的数组 $F_{a_i}$ 加起来，然后做FWT，通过贡献和求出贡献积，在逆FWT回去就能求出答案数组了。

只需要使用 $FWT$ 和快速幂，时间复杂度 $O(n +m2^m)$，期望得分 100 分。

算法八

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

这个式子，其实是可以DP计算的，令 $dp_{i,j}$ 表示前 $i$ 位任意，后 $m-i$ 位和 $j$ 相等的数，乘以 $(-1)^{|t|}$ （$t$ 是前 $i$ 位与 $j$ 的交集）的总和。

转移时只用枚举当前位变为前 $i$ 位是，是变成 $1$ 还是变成 $0$，如果第 $i$ 位变成 $1$ 还要考虑当前数字在第 $i$ 位是否为 $1$ 以决定是否要乘以 $-1$.

这个 $DP$ 的复杂度是 $O(m2^m)$的……

不过，明眼人一下子就看出来了，这个DP其实就是一个按位分层求FWT的东西……

除此之外还有一个优化，在做逆FWT的时候，由于我们只要求 $G(0)$，可以发现 $G(0)$ 就是逆变换前数组中所有的元素之和，再乘以 $2^m$ 的逆元，所以直接扫一遍求和即可，不用逆FWT，这样常数可以减小很多。

这样FWT就完全被（或者假装被）省略了……

一个用FWT推完的题代码里没有FWT也是一件有趣的事呢？

时间复杂度$O(n+m2^m)$，期望得分 100 分。

Day2

积劳成疾

from MysteryMan，题解 by C_SUNSHINE

算法

介于除了最基本的 20 分部分分，其他部分分似乎都比std难写……

于是我们直接说std做法吧！

令 $f_{m,n}$ 表示最大值不超过 $m$，长度为 $n$ 的序列的劳累度之和。

那么首先对最大值是否等于 $m$ 分类，若最大值不为 $m$ 则可以直接加上$f_{m-1,n}$。

接着考虑最大值为 $m$ 的情况，我们不妨枚举最大值第一次出现的位置 $p$，即 $a_p = m; a_{i} < m (1 \leq i \leq p-1); a_{j} \leq m (p+1 \leq j \leq n)$

可以发现，所有包含位置 $p$ 的若干个区间的劳累度都确定了（不妨即为 $c$ 个），为 $w_k$，除了这些区间，$p$ 把整个序列分成了互相独立的两个部分，根据期望线性性，这个序列的劳累度期望为左侧序列劳累度期望乘以 $m^c$ 再乘以右侧序列劳累度的期望，于是就可以 $O(n)$ 转移了。

即 $f_{m,n} \leftarrow \sum_{p=1}^{n} f_{m-1,p-1} \times m^c \times f_{m,n-p}$

时间复杂度 $O(n^3)$，期望得分 100 分。

梦中的题面

La tâche est écrite par ftiasch,

et la solution est écrite par matthew99

算法一

枚举前$m - 1$个数，算出第$m$个数的可能数量，期望得分10分。

算法二

考虑容斥，枚举有哪些数超过了限制，然后使用可重组合数算出方案数，时间复杂度为$O(2 ^ m m)$，期望得分30分。

算法三：

考虑数位DP，记录当前每一个数与限制的大小关系，然后枚举下一位的值，如果使用二进制并采用逐位逐数转移的话，时间复杂度为$O(2 ^ m m ^ 2 \log {b})$，期望得分30分。

算法四：

考虑$c = 1$，如果我们在b进制下进行数位DP，那么我们发现对于从第$x$低位，恰好有$m - x + 1$个数可以取任意$0$到$b - 1$之间的值，剩下的$x - 1$个数只能是0。首先求出$a$个取$0$到$b - 1$的数和恰好为$b$的方案数$\text{ways}_{a, b}$，考虑从低位开始进行DP，维护$sum{x_i} - n$的值，通过记录当前位的进位（或者退位）数，通过前面求出的$\text{ways}$我们很容易进行转移。由于$sum{x_i} < n$，因此最后必须退一位（也可以看成进位为-1），于是我们也很容易求出答案。

时间复杂度为$O(m ^ 2b ^ 2)$，期望得分60分。

算法五：

考虑$c = 0$，那么无非就是有一些$x_k$可以取恰好$b ^ {k + 1}$，也就是，它在前$k$位都必须取0，第$k + 1$位取1，我们很容易通过给DP加一维来实现转移，也就是记录当前有多少数必须取0，那么最开始显然这个数的数量可以任意（因为可以有任意个$x_k$恰好取了$b ^ {k + 1}$），转移就是对于第$k$位枚举$x_k$是否取了$b ^ {k + 1}$，如果取了的话，它本来就必须取0，于是必须取0的数数量不变，否则取0的数个数需要加一。

时间复杂度为$O(m ^ 3b ^ 2)$，期望得分100分。

算法六：

我们考虑从高位往低位进行数位DP，那么取0的个数最开始是$n$，这一维的转移也很好转移。

这个时候我们就不能记录进位了，我们记录从第$k + 1$位开始往后，$n - sum{x_i}$的值，如果这个值大于$m$，那么就是前面所有$x_l$全取$b ^ {l + 1}$也不可能使这个值小于等于0，于是我们只要在0到$m$中枚举，同理，我们也只要考虑这一位之后$n - sum{x_i}$在0到$m$的情况，于是我们枚举这个值，这样我们可以将复杂度降到$O(m ^ 2b ^ 2)$，期望得分100分。