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

阶梯 NIM 忘记了,那没事了

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


# Solutions

# shuffle

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

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

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

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

# god

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

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

# wanted

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

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

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

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

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

# ambition

懒得写

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

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

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

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

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

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝