【题解】Wannafly挑战赛4

T1 解方程

枚举a 和b，那么 c 唯一确定，用数组或者map 判断一下这样子的c 是否存在。

T2 小AA的数列

按位（二进制的位）考虑每位对于答案的贡献。令 $f[bit][j]$ 表示前 $j$ 个元素里第 $bit$ 位为 $1$ 的数字个数的奇偶性。考虑数列中第 $i$ 个元素为区间右端点，对于第 $bit$ 位，我们只要求出 $f[bit][i–R+1…i–L+1]$ 中有多少个元素与 $f[bit][i]$ 不相等且区间长度为偶数就可以了，而这可以用一个前缀和 $v$ 搞定。

ans $=\sum_{\text {bit }=0}^{\max } \sum_{i=L}^{n}\left(v[b i t][i-L+1]\left[f[b i t][i]^{\wedge} 1\right][i \& 1]-v[b i t][\max (i-R, 0)]\left[f[b i t][i]^{\wedge} 1\right][i \& 1]\right) * 2^{\text {bit }}$

其中第一维表示考虑第 $bit$ 位，第二维表示考虑的前缀和的位置，第三维表示前缀里第bit位为1的数字个数的奇偶数，第四维用来满足长度为偶数的要求。

T3 割草机

首先把最后的那些全是空地的行去掉（因为割草机去这些行是完全没有意义的）。

问题其实等同于割草机在什么位置选择进入下一行。令 $r[i]$ 表示第 $i$ 行最右的杂草的位置， $l[i]$ 表示第 $i$ 行最左的杂草的位置。简单来说，如果当前行i 为奇数行，那么我们会选取 $max(r[i], r[i+1])$ 的位置，偶数行选取 $min(l[i], l[i+1])$ 的位置。没有杂草的行特别处理一下。模拟一下就可以了。

T4 树的距离

首先求出 $n$ 个点的dfs 序，一棵子树 $i$ 对应了dfs 序中的连续一段 $[L[i],R[i]]$ 。我们把所有点按它到根的距离dist 排序。然后把每组询问 $i$ 按 $dist[x[i]]+k[i]$ 排序。

T5 方程的解

如果 $p = 2$ ，那么就把 $0$ 和 $1$ 分别带进去试一试就好。如果 $p > 2$ ，那么 $p$ 是奇质数，就可以把方程化成 $y^2 = t (mod p)$ 的形式，其中 $t = (a/2)^2 - b (mod p)$ 。（注意 $/2$ 在模意义下是乘以 $2$ 的逆元）这样的话就变成了检验 $t$ 在模 $p$ 意义下是否有二次剩余。首先特判掉 $t = 0$ 的情况，这个是显然有唯一解的。之后如果有二次剩余，那么一定可以把 $t$ 写成 $g^{2k}$ 的形式，其中 $g$ 是 $p$ 的一个原根，这样的话 $t$ 肯定满足： $t^{(p-1)/2} = g^{k(p-1)} = 1^k = 1$ 。相反，如果没有二次剩余，设 $t = g^u$ ，那么 $u$ 必然是奇数，所以 $u(p-1)/2$ 也不会是 $p-1$ 的倍数， $t^{(p-1)/2}$ 也不等于 $1$ ，而会等于 $-1$ 。综上，我们就只需要看 $t^{(p-1)/2}$ 是否等于 $1$ 就可以判断 $t$ 是否有二次剩余了。若 $t$ 有二次剩余，即 $t^{(p-1)/2} = 1$ ，则原方程有解，否则就无解。