2021-10-30-Test

写了 100 + 30 + 30 + 0
可以 100 + 30 + 100 + 0

阶梯 NIM 忘记了，那没事了

T3 属于是学傻了，使用到了正睿集训遇到的小技巧然后生生转成了一道 Ynoi ，然鹅以前记过的一个简单结论可以快速做出此题

# Solutions

# shuffle

给你一些二元组 $a,b$ ，求 $x,y$ 使得 $\prod_{i=1}^n (a_i^2+b_i^2) \equiv x^2+y^2 \pmod{2^{64}}$
做线性

只有两个二元组的部分分是一个提示

你考虑把 $(a^2+b^2)(c^2+d^2)$ 划一划，配成两个完全平方，然后变成了 $(ac+bd)^2+(ad-bc)^2$ 这样就可以做两个了

然后多个你就一个个做就是了

# god

一个单调不降序列，你每次可以在某个位置减去大于 $1$ 的值并要求还是单调递增序列，求先手必胜？
$q$ 次在这个序列前后加数字

考虑把差分序列建出来，你在一个地方减去值相当于在差分序列上前一个减后一个加，然后就想到于把前一个移动到后一个，然后就是阶梯 nim 游戏的板子了，动态维护一个奇数位置和偶数位置的和即可。

# wanted

一棵树，$q$ 次询问一个点对$(x,y),x\in [l1,r1], y\in [l2,r2]$ 求最大距离点对

看到这种区间连边的方式，我想到了正睿那题，放在矩阵上。

由于我们可以 $O(1)$ 算出矩阵上每个位置的值，相当于我们要求出一个矩形最大值

然后我就不会了，听说跟一道 Ynoi 很像。

正经做法是回忆起树的直径是可以合并的，然后直接线段树维护标号区间的直径即可。

# ambition

懒得写

这种最大独立集 np 问题肯定不能硬着做

考虑这是带权最大独立集，每个点权之间差的很大，所以我们从标号小的点向标号大的点连边给这张无向图定个向，此时我们边的含义就是选了指向的点就不能选我这个点，由于点权之间差距很大，可以证明，只要选一个标号大的就比选后面一连串标号小的要优秀。

那不难发现我们其实可以把选上的点标记为必败点，所以指向它的点就是必胜点，我们可以把 SG 函数写出来，最后 SG 函数为 0 的点就是选出的点。

那对于一个合法的点 $f_{i,j,k...}$ 我们可以把每一维分开考虑，相当于是在 $K$ 张一样的图上每次跑一步，所以我们的 $SG(f_{i,j,k...}) = SG(f_i)\oplus SG(f_j)......$

把柿子写出来，再上一个 FWT 优化即可。