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搞定。
其中第一维表示考虑第bit位，第二维表示考虑的前缀和的位置，第三维表 示前缀里第bit位为1的数字个数的奇偶数，第四维用来满足长度为偶数的要求。
首先把最后的那些全是空地的行去掉（因为割草机去这些行是完全没有意义的）。
问题其实等同于割草机在什么位置选择进入下一行。令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，则原方程有解，否则就无解。
全部评论
(0) 回帖