论上一场发挥一般这一场发挥超差却来只给第二场写题解是什么心理.jpg
T1 结论猜错，T2 没交成，今天太浪了……
A. 涂色游戏
不妨设 p1<p2。
（相等的情况完全可以不管）
首先 1020 的范围限制可以当 ∞，因为 lcm(p1,p2)≤1018。
那么容易发现，最长的连续段一定全是 p1，即是夹在 p2 的两个相邻的倍数中间。
设这两个倍数为 mp2,(m+1)p2，再设 n=minipi>mp2i,w=max(n+i)p1<(m+1)p2i。
那么显然有 mp2<np1<(n+1)p1<⋯<(n+w)p1<(m+1)p2
把 (mp2,(m+1)p2) 看作一个滑动窗口直观地感受，易得当 np1−mp2 最小时 w 最大。
设 t=np1−mp2，那么根据裴蜀定理可知当 gcd(p1,p2)∣t 时才有解。
求 t 的最小值，那么显然就是 gcd(p1,p2)。
有了 t 的最小值如何求 w？
易知 w=⌊(m+1)p2−np1−1p1⌋。
由于 t=np1−mp2，所以 (m+1)p2−np1=p2−t。
故 w 为 ⌊p2−t−1p1⌋。
注 意 特 判 k = 1！
（考试上都没搞出来的我有什么资格说这话）
B. 子序列问题
数颜色题有一个套路，那就是对于每种颜色，考虑找一个点来代表这种颜色的贡献。
从 n 至 1 枚举 l，同时维护每一种颜色在 [l,n] 中第一次出现的位置。
那么对于所有 [l,r]，这种颜色对其有贡献的条件就是 r 不小于这种颜色在 [l,n] 中第一次出现的位置。
满足条件的 r 显然是一个区间，那么考虑区间修改，求区间平方和即可。
使用线段树即可维护。
（注意卡常）
C. 游戏
考场有思路，但是半看错题 + 半假做法 + 太浪（甚至导致失了前面的分）。
首先，这题有一个重要的地方在于操作是不区分顺序的。
也就是说实际上操作的方案只有 m! 种（钦定一个人的顺序，另一个人随便排）
考虑设 f(k) 表示恰好 k 次非平局，g(k) 表示至少 k 次非平局。
那么有 g(k)=m∑i=k(ki)f(i)
由二项式反演有 f(k)=m∑i=k(−1)i−k(ki)g(i)
那么只需要求 g 即可。
考虑设 fi,j 表示 i 的子树内选择 j 组有子孙后代关系且不属于同一个人的点的方案数。
转移就是一个树形背包，同时注意考虑当前点与其子树内点所产生的一组贡献。