4月CWOI杂题

tips：为了避免一不留神题目就被邪恶的 o 老师隐藏，题面文件在 cnblogs 上有备份。

C0216 【0407 C组】模拟测试

这场比赛四道题代码加起来长度不超过 1500 个字符，赢！（223+399+330+541=1493）

A 【1231 C组】数组计数

定义 \(f_{i,j}\) 表示前 \(i\) 个数，和为 \(j\) 的方案数，前缀和优化转移。时间复杂度 \(\text{O}(nk)\)。

B 【1231 C组】旅行

因为终点是固定的 \(a_i\)，考虑把路径转化成找到一个以 1 为起点和终点的环再减去从 \(a_i\) 到 1 的部分。发现这样问题就等价于给你一些点，找到一个最短的联通所有点的边集，这个环会经过其中每条边两次。每次加点的时候一直向上跳到已有的路径上。因为每个点只经过一次，时间复杂度 \(\text{O}(n)\)。

C 【1231 C组】进化

因为数据给了 \(T=2^d\) 的部分分，这使我们联想到如果能在 \(\text{O}(n)\) 的时间内解决 \(T=2^d\) 的情况，就可以做到 \(\text{O}(n\log T)\) 了。

首先 \(b_i=(a_{i-1}+a_{i+1})\bmod 2=a_{i-1}\oplus a_{i+1}\)。一次进化后，\(a_i\) 会对 \(a_{i-1},a_{i+1}\) 产生贡献；两次进化后，\(a_i\) 会对 \(a_{i-2},a_{i-1},a_i,a_{i+1},a_{i+2}\) 产生贡献 \(\ldots\) 也就是说，“\(a_i\) 在 \(T\) 次进化后会对 \(b_j\) 造成贡献的次数”等于“令 \(s_k=\sum\limits_{t=1}^kx_i\)，满足 \(i+s_k\in[1,n]\) 的，长度为 \(T\) 且只包含 \(1,-1\) 的，\(i+s_T=j\) 的数列 \(x\) 的个数。

发现这个 \(i+s_k\in[1,n]\) 的限制很麻烦，考虑把 \(a_i\) 变成一个如图所示的环：

即 \(c_0=c_{n+1}=0,c_i=c_{2n+2-i}=a_i\)。发现对 \(c\) 进化和对 \(a\) 进化是一样的，这很显然。

令 \(m=2n+2\)，\(c_i\) 真正会对 \(c_{(i+x-(T-x))\bmod m}\) 产生影响当且仅当 \(c_i\times\binom{x}{T}\equiv 1\pmod 2\)，即 \(c_i=1,\binom{x}{T}\equiv 1\pmod 2\)。因为我们此时的 \(T=2^d\)，由 Lucas 定理 可知只有当 \(x=0,T\) 时才满足上述条件，即 \(c_i\) 只会影响 \(c_{(i+T)\bmod m},c_{(i-T)\bmod m}\)。一次操作时间复杂度 \(\text{O}(n)\)，总时间复杂度 \(\text{O}(n\log T)\)。

D 【1231 C组】Y老板的别墅

定义 \(f_{i,j}\) 表示只考虑 \([i,j]\) 间的房子（可以认为在 \(i-1,j+1\) 处各有一栋无限高的房子）的方案数。转移就是枚举当前范围内最高的楼 \(k\)，满足 \(r_k=\min(k-i,j-k)\)，\(f_{i,j}\leftarrow f_{i,j}+\binom{k-i}{j-i}\times f_{i,k-1}f_{k+1,j}\)。解释一下：乘组合数是因为我们只规定了范围内每栋房子的相对高度。

发现对于一个 \(k\)，满足 \(r_k=\min(k-i,j-k)\) 的 \(i,j\) 很少，所以总的转移是 \(\text{O}(n^2)\) 的。