..
LibreOJ β Round #4
T1. 游戏
X 为实数意味着 X 可以填任何数，那么当 $n \gt 1$ 时先手和后手都可以通过 X 的值任意改变逆序对的奇偶性。
所以只要 X 为奇数个先手必败，否则先手必胜。
当序列中没有 X 时求逆序对即可。
注意特判 $n = 1 $ 时先手必败。
T2. 多项式
根据扩展欧拉定理，$x^a \equiv x^{a + \varphi(k)} \pmod k$。
令 $a = \varphi(k)$，则有 $x^{\varphi(k)} \equiv x^{\varphi(k) + \varphi(k)} \pmod k$。
$2 \times \varphi(k)$ 次多项式 $f(x) = x^{2 \times \varphi(k)} - x^{\varphi(k)}$ 即为所求。
注意 $k = 1$ 时无解。
T3. 子集
将满足关系 $\gcd(a_i, a_j) \gcd(a_i + 1, a_j + 1) \ne 1$ 的点对 $(i, j)$ 连边，求最大团，即补图的最大独立集。
注意到当 $a_i, a_j$ 奇偶性相同时一定连边，因此补图一定是二分图，最大独立集大小即点数减去最大匹配数。
T4. 框架
预处理每个位置向右向下延伸的最长长度，枚举正方形左上角及边长统计答案。
时间复杂度 $\mathcal O(n^3)$，实际跑不满。
T5. 求和
有反演公式 $\mu^2(n) = \sum_{d^2 \vert n} \mu(d)$。
于是有
\[\begin{aligned} & \sum_{i = 1}^n \sum_{j = 1}^m \mu^2(\gcd(i, j)) \\ = & \sum_{i = 1}^n \sum_{j = 1}^m \sum_{d^2 \vert \gcd(i, j)} \mu(d) \end{aligned}\]枚举 $d$ 计算答案。