这次的题目背景大部分是vfleaking写的。

出题人 01,02,03 只是主人公的名字，和真实出题人没有任何的关系。

序列妙妙值

from zhouyuyang，数据、标程、题解 by zhouyuyang。

由于是 D1T1 ,为了让参赛的选手分数都好看一点，数据相对来说造的没有那么强。

算法1

我会暴力!

设$f_{i,j}$表示前$i$个数字，划分成了$j$段的最优解。

转移直接枚举新的右端点即可。

使用前缀异或和优化后时间复杂度为$O(kn^2)$。

期望得分:$40$。

算法2

我会优化暴力!

当$a_i$较小时，则我们可以记录前缀异或和为$a_i$的最优解。

转移时枚举上一个端点对应的前缀异或和即可。

设$v=\max{a_i}$，则时间复杂度为$O(knv)$

期望得分:$20 \sim 40$。

结合算法1期望得分$60 \sim 80$。

算法3

不难发现对于算法2，我们可以实现$O(1)$修改最优解，$O(v)$查询。现在我们尝试平衡一下两部分的复杂度。

在修改时，我们枚举二进制下较高的$8$位，并且更新最优解。

在询问时，我们枚举二进制下较低的$8$位，并且利用最优解更新$DP$值。

不难发现，这样转移和算法2中的等价。

时间复杂度$O(nk\sqrt{v})$。

期望得分:$100$。

其他算法

考虑序列分块，块内暴力转移，块之间采用fmt的思路转移，时间复杂度$O(kn\sqrt{n \log n})$，当场看上去是能过的。

可以尝试只枚举xor和前$256$小的状态加速转移，得分不明。

可以尝试在$trie$树上乱搞更新答案，得分也不明。

网络恢复

from Aprilgrimoire，数据、标程、题解 by Aprilgrimoire。

做法一

令所有的$a_i=1$，依次对每条边进行询问。

询问次数：$O(m)$

期望得分：$10$

做法二

每次取出$w=64$个点，令它们的权值$a$分别为$1,2,\cdots,2^{w-1}$。然后打开每条边，进行询问。通过每个点的$b$的每个bit可以判断出它和这$w$个点中的哪些点有边。

询问次数：$O(\frac{n}{w})$

期望得分：$30$

做法三

测试点$5$中，保证给出的图是树。我们可以给每个点分配随机的$a$，打开每条边，进行询问。对于图中的叶子，它的$b$恰好等于和它相连的点的$a$。对于其它点，它的$b$等于某个点的$a$的概率是很低的，可以忽略。依次考虑所有的点，如果我们发现它是叶子，那么我们就找到了一条边。我们可以报告这条边，并且把这条边从图上删掉（将它的两个端点的$b$异或上对方的$a$），并重新考虑这条边的端点是否成为了叶子。

询问次数：$1$

期望得分：$10$

做法四

测试点$6$中，保证给出的图是基环树。每次随机将边分成两个集合。由于环上至少有$3$条边，每次至少有$\frac{3}{4}$的概率使环上的边没有被划分到同一个集合中，从而得到的两个集合都是森林。尝试对这两个集合使用做法三，有较高的概率可以得到解。

询问次数：$O(1)$

期望得分：$20$

做法五

每轮随机取出一些边，只考虑被取出的边。每条边在不同的轮中可以被重复取出。使用做法三的方法持续找出度为$1$的点，直到剩下每个点的度都至少为$2$。每条边有玄学的概率在至少一轮中被发现了。

虽然不知道为什么但是效果还不错。

询问次数：$50$

期望的分：$80$

做法六

将所有的边随机分成$50$组，只考虑某一组中的边。使用做法三的方法持续找出度为$1$的点，直到剩下每个点的度都至少为$2$。假设当前剩下的每个点的度都至少为$k$，我们可以找出这些点中任意$\lfloor(k+1)/2\rfloor$个的$a$的异或和，设为集合$A$。再考虑一个点的$b$异或上$\lfloor k/2 \rfloor$个点的$a$，设为集合$B$。比较集合$A$与集合$B$，对于每个公共元素，我们就找到了将一个点的$b$表示为$k$个$a$的异或的方法。发现一些度恰好为$k$的点并删除和它们相邻的边后，可能有一些点的度现在小于$k$了。由于剩下的点数比较少，我们可以重新把$k$置为$1$，然后依次增大$k$。

虽然不知道为什么但是对于随机数据效果挺好的。

询问次数：$50$

期望得分：$100$

校园闲逛

from zhouyuyang，数据、标程、题解 by zhouyuyang。

本题idea来自于【CTSC2016】NOIP十合一的测试点$4$。

出题人没打算把FFT的常数卡到死，被喷卡常题，然后就被分治干过去了...

算法-1

暴力DP计算方案数即可。

时间复杂度$O(nmv)$。

期望得分$10$。

算法0

使用分治fft优化暴力计算的过程。

时间复杂度$O(n^3v\log^2v)$。

转移时利用点值的性质可以做到$O((n^3+n^2\log v)v\log v)$

期望得分$20 \sim 100$。

同样是算法0，为什么有人20，有人100...

选手卡常水平高超，实在打不过...告辞...

算法1

确定起点时可以列出关于答案的生成函数的方程组：

假设$a_{p,i}$表示长度为$i$的到达$p$的路径条数，$e_{p,q,i}$表示起点是$p$,终点是$q$,长度是$i$的边的数量。据此设$A_p=\sum a_{p,i}x^i$,$E_{p,q}=\sum e_{p,q,i}x^i$

设节点数为3,起点为1。则可以列出如下方程组。

$$ \left\{ \begin{array}{l} A_1=E_{1,1}A_{1}+E_{2,1}A_{2}+E_{3,1}A_{3}+1\\ A_2=E_{1,2}A_{1}+E_{2,2}A_{2}+E_{3,2}A_{3}\\ A_3=E_{1,3}A_{1}+E_{2,3}A_{2}+E_{3,3}A_{3}\\ \end{array} \right. $$

类似于高斯消元的思路，我们可以每次找到唯一一个常数项非$0$的系数进行高斯消元。由于边权不为0，因此仅有形如$E_{i,i}$的系数的常数项非$0$。

解到最后会得到若干个$A_if_i=P_i$的公式，由于$f_i$常数项非0，直接$A_i=P_if_i^{-1}$即可,其中$f_i^{-1}$表示$f_i$的逆元。

对于每个起点运行消元即可。

时间复杂度$O(n^4v\log v)$。

期望得分$50 \sim 80$。

算法2

观察不同起点时的矩阵，不难发现方程组本质只有最后一列的常数项上存在区别，其余各项均没有区别。

因此类比于解逆矩阵，我们可以同时解这$n$个方程，在消元时同时消最后的$n$个不同的方程即可。

时间复杂度$O(n^3v\log v)$。

期望得分$60 \sim 100$。

算法3

在维护高斯消元的系数的时候，仍然可以使用点值加速高斯消元系数的维护。

我们只需要在询问当前元素的值的时候进行一次IDFT，其余时间全部使用点值维护修改量即可。

时间复杂度$O(v(n^3+n^2\log v))$。

期望得分$70 \sim 100$。

由于算法$3$有着高达$7$的大常数，但是算法$2$常数只有$1$，因此算法$3$跑的挺慢的。

其他算法

如果利用FFT的点值，不要每次都暴力分治也可以过。复杂度可以和算法3一样。

如果在转移的时候利用转移系数加速分治过程也可以过。复杂度可以和算法3一样。

如果你分治常数足够小，应该可以卡着时间限制过去。