切割冰片

idea, data, solution, std from ix35

在题解中，我们用横光 $i$ 表示从上到下第 $i$ 条横向光束，纵光 $i$ 表示从右到左第 $i$ 条纵向光束（与题面相反）。

称一根光束被阻塞，当且仅当它最终没有延申到其最远距离。

算法一

暴力枚举所有 $n+m$ 条光束的激活顺序。

时间复杂度为 $O((n+m)!\times \mathrm{Poly}(n,m))$。

期望可以通过子任务 1，获得 15 分。

算法二

我们对该问题做一些基本的观察。

• 观察 $1$：横光 $1$ 和纵光 $1$ 中，一定存在一个没有被阻塞。

  证明：假设二者都被阻塞，则第一种情况是横光 $1$ 被纵光 $1$ 阻塞，那么纵光 $1$ 就没有被阻塞，矛盾；第二种情况是横光 $1$ 被纵光 $x(x>1)$ 阻塞，纵光 $1$ 被横光 $y(y>1)$ 阻塞，那么横光 $y$ 和纵光 $x$ 就会相交且穿过对方，这是不合题意的，矛盾。

据此，我们就可以推得更强的结论：

• 观察 $2$：可以假定所有横光从上到下依次激活，所有纵光从右到左依次激活，不会漏掉任何一种可能的最终结果。

  证明：由于横光 $1$ 和纵光 $1$ 中存在一个没有被阻塞，所以可以认为那一根光束是第一个被激活的，然后对剩余的光束归纳。

于是我们只需要枚举满足上述规则的方案，当 $n=m$ 时时间复杂度为 $O(2^{2n})$。

期望可以通过子任务 1 与子任务 2，获得 30 分。

算法三

我们可以考虑按照激活的顺序进行动态规划。

设 $f(i,j)$ 表示只考虑横光 $1,\dots ,i$ 和纵光 $1,\dots ,j$，共能得到多少种不同的光束排布方法，那么转移如下：

• 如果 $l_{n-i+1}<m-j+1$，那么横光 $i$ 即使伸到最远也够不着纵光 $j$，所以我们可以认为横光 $i$ 是最后一个被激活的（因为把所有纵光激活的时间移到它前面不影响结果），也就是 $f(i,j)=f(i-1,j)$；
• 如果 $l_{n-i+1}\ge m-j+1$，那么横光 $i$ 是可能挡住纵光 $j$ 的，所以最后一个激活的是横光 $i$ 还是纵光 $j$ 就是两种不同的情况，也就是 $f(i,j)=f(i-1,j)+f(i,j-1)$。

初始状态为 $f(0,i)=1,f(i,0)=1$，答案为 $f(n,m)$。

直接计算，时间复杂度为 $O(nm)$。

期望可以通过子任务 1 ～ 4，获得 80 分。

算法四

我们需要针对 $m$ 这一维进行优化。

考虑从 $f(\ast ,x-1)$ 推到 $f(\ast ,x)$，设 $S_x$ 表示满足 $l_{n-i+1}<m-x+1$ 的 $i$ 的集合，那么对于 $i\in S_x$ 有 $f(i,x)=f(i-1,x)$，而对于 $i\notin S_x$ 有 $f(i,x)=f(i-1,x)+f(i,x-1)$。

显然 $S_x\subseteq S_{x-1}$，不妨先考虑 $S_x=S_{x-1}$ 的特殊情况：

• 这时，我们将所有那些 $i\notin S_x$ 的 $i$ 写出，排序后记为 $0=a_1<\dots <a_k$，那么对于 $i\in S_x$，找到最大的 $a_j$ 使得 $a_j<i$，就有 $f(i,x)=f(a_j,x)$，所以我们可以只关心所有 $f(a_j,x)$。
• 而对于 $j>1$，我们有 $f(a_j,x)=f(a_j-1,x)+f(a_j,x-1)=f(a_{j-1},x)+f(a_j,x-1)$，也就是说 $f(a_j,x)(j=1,\dots ,k)$ 这个序列实际上是由 $f(a_j,x-1)(j=1,\dots k)$ 这个序列做前缀和得到的。

扩展上面这个结果，如果有 $S_x=S_{x+1}=\dots =S_{x+t}$，那么 $f(a_j,x+t)$ 这个序列就应该是由 $f(a_j,x)$ 这个序列做 $k$ 次前缀和得到的，利用路径计数的模型，通过预处理组合数可以 $O(n^2)$ 计算长度为 $n$ 的序列做若干次前缀和得到的结果。

再考虑 $S_x\ne S_{x+1}$ 的情况，由于 $S_{x+1}\subseteq S_x$，所以这样的 $x$ 只有 $O(n)$ 个，我们可以对于这些 $x$ 暴力进行转移。

所以总的时间复杂度为 $O(n^3)$。

期望可以通过所有子任务，获得 100 分。

科考工作

idea from JohnVictor; data, solution, std from csy2005; solution2 from 127

算法一

考虑如下做法：如果众数出现至少 $n$ 次，直接输出众数；否则考虑每一次将众数和第二多的数配对，可以配出 $n-1$ 对不同的对子。

我们证明存在一组解，使得选了剩下一个数和这 $n-1$ 对中每一对中的一个数。这等价于说，对于任意 $n-1$ 个非零数，他们的子集和取遍 $modn$ 的完系。

实际上，我们可以归纳的找出 $\{0\}=S_0\subseteq S_1\cdots \subseteq S_{n-1}={\mathbb{Z}}_n$，并且 $|S_i|=i+1$，且由前 $i$ 个数的子集和构成。

令第 $i$ 个数为 $a_i$，我们只用证明 $(S_{i-1}+a_i)\setminus S_{i-1}$ 非空，实际上两者大小相同，并且模素数意义下如果 $S_{i-1}+a_i=S_{i-1}$，那么对于 $S_{i-1}$ 中任意一个元素 $t$ 和任意的 $k$，$t+k{a}_i$ 都在 $S_{i-1}$ 中，那么 $S_{i-1}$ 就是全集，矛盾。

我们可以很方便的用 set::bitset 来维护每一次加进去的数，也很好根据维护好的数组来逆推答案。时限很松，$O(\frac{n^2}{w})$ 的做法基本都能获得 $90$ 分。

为了获得 $100$ 分，有很多乱搞可以通过。例如在上面一步中将所有相同的数写在一起的前提下 random_shuffle 大概率能找到一个区间作为解。

算法二

经典的modular subset背包，考虑对于一个当前的 $x$ 找到一个 $t$ 在当前的背包中而 $t+x$ 不在,这在 bitset 上就相当于把一个 0/1 串移位与自己作或，而要均摊地找到那些对应位置不同的元素（在模意义下不同的元素是我们要找的元素的两倍），可以发现我们可以使用二分 + hash 来跳过一段完全相同的部分，而动态的修改需要使用一个树状数组来维护hash，于是复杂度为 $O(n{\log }^{2}n)$，可以通过本题 。

谢罪环节

今天比赛的B题是来源于 UNR d2t1，经典的数学问题，给出了存在性证明，但是复杂度不够好，需要找到一个构造性的算法。

JV 出这题主要是希望讨论MO中剩余类递推的思想，也就是对于一个集合 S，如果 S 和 S+x 在模素数意义下是相同的，那么 S 必定是全集。从这里很好给出一个配对，然后给出 n^2/w 的背包，这是 JV 投题时给出的做法。

后半部分，如果直接用位运算优化，那么可以获得 90 分。最后的 10 分数据范围较大，主要还是因为我们朴素地想，要出题就尽可能出到最大可能的范围。

由于获得这最后 10 分需要知道一点论文上的解题套路（虽然近期也出现在了其他模拟赛中），所以对于不熟悉这一解题套路的同学来说不太公平。对此我们深表歉意，下次出题时我们会尽量避免这种情况，比如魔改题意使得论文上的结果无法被使用。

企鹅游戏

idea, data, solution, std from Alex_Wei; data2, std2 from djq_cpp, csy2005

算法一

暴力匹配，时间复杂度 $\mathcal{O}(L^2)$。

期望通过子任务 1，得到 20 分。

算法二

注意到对每个 $t_j$ 最多只有 $|t_j|$ 个 $|s_i|$ 产生贡献，因此问题转化为 $\mathcal{O}(L)$ 次求某个模式串在文本串中的出现次数。对 $s$ 建出 AC 自动机（相当于对最长的 $s_i$ 建出 KMP 自动机），将 $t_j$ 放在自动机上跑一遍，则 $s_i$ 在 $t_j$ 中的出现次数相当于它在自动机上对应节点在失配树上的子树内所有节点被经过的次数之和。树形 DP + 快速幂或光速幂即可。

时间复杂度 $\mathcal{O}(L\log P)$ 或 $\mathcal{O}(\sqrt{P}+L)$，其中 $P=2^{32}$。

期望可以通过子任务 2，获得 20 分。结合算法 1 可以获得 40 分。

算法三

容易证明 $|s_i|$ 至多只有 $\mathcal{O}(L^{1/2})$ 种取值。

因为 $s_i$ 互不相同，所以对于每个 $t$ 的前缀 $t[1,j]$，对于每个不同的长度 $len$，至多有一个长度为 $len$ 的 $s_i$ 和 $t[1,j]$ 的后缀匹配。因此和 $t[1,j]$ 的后缀匹配的 $s_i$ 数量不超过 $|s_i|$ 的取值种类数，即 $\mathcal{O}(L^{1/2})$。

建出 $s_i$ 的 AC 自动机，对每个状态预处理最近的代表某个单词的祖先，那么每跳一次祖先就会找到一个和当前前缀的后缀匹配的单词。暴力统计所有出现单词的 $cn{t}_i$，最后光速幂算出 $v_i$ 即可。时间复杂度 $\mathcal{O}(L^{3/2})$。

期望可以通过子任务 1 与子任务 3，获得 50 分。结合算法 2 可以获得 70 分。

算法四

我们还有另一用于解决子任务 3 的算法：

根号分治，对于串长 $\le \sqrt{L}$ 的 $t$，枚举所有子串更新 $cn{t}_i$。对于串长大于 $\sqrt{L}$ 的 $t$，对每个 $s_i$ 求出其在 $t$ 中出现次数，算出 $v_i$ 并求和。时间复杂度 $\mathcal{O}(L^{3/2})$。

同样地，期望可以通过子任务 1 与子任务 3，获得 50 分。结合算法 2 可以获得 70 分。

算法五

结论：每个文本串包含的 不同 单词数之和的级别为 $\mathcal{O}(L^{4/3})$。

证明：长度超过 $L^{1/3}$ 的单词最多有 $L^{2/3}$ 个，每次出现对应一个长度超过 $L^{1/3}$ 的文本串，所以在所有文本串中最多出现 $L^{2/3}$ 次。对于长度不超过 $L^{1/3}$ 的串，每个长度的所有单词出现次数之和不超过 $L$，因此总和不超过 $L^{4/3}$。

也就是说，在 Subtask 3 的做法中，若将重复经过的点去掉，则总共只会遍历 $\mathcal{O}(L^{4/3})$ 个点。基于此结论，建出 $s_i$ 的 AC 自动机，为避免重复经过同一点，有两种做法：

• 将 $t$ 在 AC 自动机上经过的所有点建出虚树，树形 DP + 暴力枚举。
• 从 $t$ 在 AC 自动机上经过的每个点向上跳父亲，如果当前点被经过，说明它的祖先一定被经过，退出。这个过程给予所有相关点形成的树的形态，对其做拓扑排序即可。

配合光速幂，时间复杂度 $\mathcal{O}(L^{4/3})$。为了卡掉所有 $L^{3/2}$ 的做法，时限设置较小（但是在两倍 std 以上）。不使用光速幂会被卡，常数较大也有概率被卡。

期望可以通过所有子任务，获得 100 分。

Bonus

本题可以做到 $\mathcal{O}(L\sqrt{\log L})$，但常数较大。

对于单次询问，考虑将对应虚树建出，问题形如求一条链上所有单词节点出现 $k$ 次的权值之和。将所有链离线按 $k$ 分类处理，则通过树上差分可将处理的复杂度降至所有 $cnt=k$ 的链的并的大小之和，严格优于 Subtask 4。

通过上述分析，可知时间复杂度为每个单词在所有文本串中的不同出现次数之和。

如果一个单词的贡献为 $x$，那么它至少出现了 $\mathcal{O}(x^2)$ 次。

设长度为 $i$ 的单词有 $c_i$ 个，它们在文本串中的出现次数之和不超过 $L$。根据 $\sqrt{x}$ 的上凸性，这 $L$ 次平均分配给 $c_i$ 个单词再求平方根后最优。因此 $c_i$ 的贡献为 $c_i\times \sqrt{{\displaystyle \frac{L}{c_i}}}$ 即 $\sqrt{L{c}_i}$。

将 $\sqrt{L}$ 提出，设 $d=i{c}_i$，我们需要在 $\sum d_i\le L$ 的限制下最大化 $\sum \sqrt{{\displaystyle \frac{d_i}{i}}}$。根据 $\sqrt{{\displaystyle \frac{d_i}{i}}}$ 的上凸性，我们会分配 $d_i$ 使得 $\sqrt{{\displaystyle \frac{d_i}{i}}}$ 的导数相同，即 $\sqrt{{\displaystyle \frac{1}{i\times d_i}}}$ 相等。因此 $d_i$ 正比于 ${\displaystyle \frac{1}{i}}$，得 $d_i=L\times {\displaystyle \frac{\frac{1}{i}}{\sum \frac{1}{i}}}={\displaystyle \frac{L}{i\ln L}}$。

因此时间复杂度为 ${\displaystyle \mathcal{O}(\sqrt{L}\times \sum \sqrt{\frac{L}{i^2\ln L}})=\mathcal{O}(L\sqrt{\log L})}$。

谢罪环节

出题人没想到有依赖模数性质的 $32L$ 做法，在这里拜谢 skip2004 哥哥！

有一位同学写正解被卡常了，还有一位同学 $O(L\sqrt{L})$ 极限卡常通过此题，出题人为没卡掉暴力反倒把正解卡了表示遗憾，并在此谢罪 QAQ。欢迎各位选手发挥自己的聪明才智卡掉根号的做法！

出题人出题时就感觉很难区分 $O(L\sqrt{L})$ 和 $O(L^{4/3})$。在标算只有 $O(L\sqrt{L})$ 时，出题人本打算将此题投到西安区域赛来着，后来写题解写着写着发现有 $O(L^{4/3})$ 做法，觉得很高妙，想分享给大家，所以就投 UOJ 了。

出题人尽自己最大的努力将这两个复杂度已知的所有算法卡满了。出题人的想法是，既然投到了 UER，那就尽量符合 “Easy” 的原则让大家乐呵乐呵。更重要的是借此机会把这个有趣的结论推广给大家，希望大家喜欢！