A
求出 $n$ 个数都是不到 $m$ 质数，且 Nim 游戏后手必胜的方案数。
$n \le 10^9,m\le 10^6$ 给定模数。
考虑到质数没啥好的性质，看起来也只能够去算这个异或卷积 $n$ 次方。
但是直接写完发现这东西巨慢无比。考虑怎么优化常数。
可以发现最后只需要求 $A[0]$ ，这个数在异或卷积式子可以看出为所有数的和，而 $\text{IFWT}$ 在异或卷积其实就是做一次 $\text{FWT}$ 然后每个数除以 $len$ 。因此我们最后没必要做一次 $\text{IFWT}$ ，直接求所有数的和除以 $len$ 即可。
然后会发现由于模数不固定每个数做一次 $n$ 次幂巨慢无比。但是做一次 $\text{FWT}$ 后每个数的绝对值不会超过之前所有数的和，而之前所有数的和，即质数个数，是 $O(\frac n{\ln n})$ 级别的，对 $1 \sim 2.5\times 10^5$ 预处理 $n$ 次方即可。这样就可以跑得很快了！
1 |
|
B
定义零一序列 $S(k) = \{\lfloor \frac{i}{k} \rfloor\bmod 2 \}$ 。
给定一个序列 $A_{1 \dots n}$ ，你需要把它变成一个常数序列，常数为非负整数，你可以进行的操作是选择一个 $2^k \le m$ ，然后选择 $S(2^k)$ 的一个长为 $n$ 的子序列，然后给 $A$ 的对应位置减去这个序列。求最少需要进行的操作数量。
$n \le 10^7 , m \le \frac{n}{2} , m = 2^t$
我们考虑当 $n > 2m$ 的时候会发生什么。不难发现即使你选择最大的 $2^k$ ，你能做到的影响也是具有循环节的，循环节为 $2m$ 。所以可以直接砍掉 $2m$ 后面的部分，它们必须和前面相同。
然后会发现当你选择一个 $2^t < m$ 的时候，循环节必然是小于等于 $m$ 的，那么它对前 $m$ 和后 $m$ 的影响必然是完全相同的。所以就有了这么一个想法，我们先使用 $S(2^t = m)$ 的子序列操作，用尽量少的操作使得前一半和后一半对应位置完全相同，然后再开始递归用较小的操作。而可以发现这样的操作次数也是最少的，因为操作是无序的，所以可以从大到小来排列操作，在你用完最大的操作的时候需要满足前后对应相等显然是必要的，所以你从大到小都是用最少的操作来达成这个就一定可以得到最优的操作序列。
然后现在只需要考虑怎么用 $S(m)$ 的字序列来操作把前 $m$ 个和后 $m$ 个整成对应位置相等的。直接做看起来比较不行，我们考虑区间加一 / 前缀后缀加一这两个东西如果差分后就可以转成很少的位置做加减。因此可以对前一半和后一半分别差分。然后操作就有两种。如果是 $[l,l+m - 1]$ 减 $1$ ，就是 $l$ 位置的差分减 $1$ ，$l + m$ 位置加 $1$ ，然后给第二个序列差分的开头减 $1$ ，另一种是除 $[l,l+m-1]$ 的位置减 $1$ ，那么就是开头 减 $1$ ，然后给 $l$ 加 $1$ ，给 $l + m$ 减 $1$ 。
所以我们可以用这两种操作把除开前后差分的第一个位置给做成对应位置相同。然后最后可以使用 $11\dots 1100\dots 00$ 和 $00 \dots 0011\dots 11$ 两种操作把两半差分的开头调整好。
这样做复杂度是 $n + \frac n 2 + \cdots$ 的，也就是 $O(n)$ 。
1 |
|
C
给定一棵启发式的线段树，具体来说，给定 $2n-1$ 个区间，保证这些区间可以形成线段树的结构。然后有两种操作，要么进行一次与
splay相同的rotate操作，要么询问当对区间 $[l,r]$ 进行询问时，会访问多少节点。
首先考虑这个 rotate 操作，手玩一下会发现每次操作只会改变 $O(1)$ 个区间。
然后考虑怎么进行询问。暴力上线段树肯定是不行的。考虑看成一个偏序问题，如果直接算被这个区间包含的所有线段树区间肯定是会挂的。但是线段树有一个优秀性质：子树中叶子个数减去非叶子个数正好是 $1$ ，所以统计极大子树的数量可以直接给叶子权值设为 $1$ 非叶子设为 $-1$ ，然后统计所有被包含的区间和即可。
这题卡空间，但是可以离线下来，跑 CDQ 分治即可。复杂度 $O(n\log^2 n)$ 。我场上就是这个做法。
如果想要变成 $O(n\log n)$ 需要观察性质，可以发现求的其实就是一个点到根路径上的左儿子个数以及右儿子个数。但是其实写出来还不如两个 $\log$ 快。
1 |
|