复盘
T1 看上去不难。一开始以为枚举 \(a, b\)，然后考虑平方差。于是想出了 这道题 的解法。但是转化不过去。后来发现因为 \(k\) 很小直接暴力预处理就行。30min 左右过大样例。
T2 一眼不会。想到了 P1521 求逆序对 但还是不会做。
T3, T4 显然不可做。有了前几场的经验，先把所有特殊性质+暴力分打了。不到 11:00 算得分 \(100+26+36+44\)。
对拍 T1 + T3 基环树。
剩下时间都在想 T2 的状压 DP。然后 T4 做了个随机的 \(20\) 部分分。
离场。最终 \(100+26+(20,36)+40 = 204\)。T3 最开始交错了代码。T4 因为没有兼容 Sub2,3 导致 Sub2 全挂。
补题 \(100+100+56+64 = 320\)。
总结
不足：
- subtask 分类出错（老毛病）
题解
A. Sing Alive
枚举 \(c, d\)。问题变成求有多少 \(a, b\) 满足 \(a^2+b^2=d^2+k-c^2\)。注意到 \(a, b \le n \le 2000\) 所以暴力预处理即可。
这个题没有难度。说一下赛时想到的另一个题 U488066 Sing Alive 2。这里省去了枚举 \(a, b\) 一步，但是 \(k\) 变大，且 \(c, d\) 少去了 \(\le n\) 的限制。
标签：约数,10.7,dfrac,equiv,100,kx,模拟,2k From： https://www.cnblogs.com/2huk/p/18450364首先平方差 \((c-d)(c+d)=k\)。
这两个东西一定都是 \(k\) 的约数。我们设 \(c-d=x\)（\(x \mid k\)），那么另一个一定可以表示成 \(\dfrac kx\)。
但是这样的正整数对 \((x, \dfrac kx)\) 能对应几个 \((c, d)\)？不难发现最多两个。即当 \(x \equiv \dfrac kx \pmod 2\) 时，\(c=\dfrac 12 (x+\dfrac kx),d=x-c\) 是唯一一组解。
于是问题变成了：求有多少 \(k\) 的约数 \(x\) 满足 \(x \equiv \dfrac kx \pmod 2\)。
分类讨论：
- \(k\) 为奇数：那么 \(k\) 的约数一定也是奇数。所以 \(x\) 可以是 \(k\) 的约数中的任意一个。求 \(k\) 的约数个数即可。
- \(k\) 为偶数：设 \(k = 2k_0\)。那么 \(x \equiv \dfrac kx \equiv 1 \pmod 2\) 显然不合法。所以 \(k, \dfrac kx\) 都需要是偶数。设 \(k = 2k_1, \dfrac kx = 2k_2\)，则原式为 \(2k_0=2k_1+2k_2\)，即 \(k_0=k_1k_2\)。此时我们对 \(k_1,k_2\) 的奇偶性没有要求。于是答案是 \(k_0\) 的约数个数。
这样做答案会大一倍。原因是