2021“MINIEYE杯”中国大学生算法设计超级联赛（1）

终于有一个队友了，感动。团队复健中。

AC Codes

打表找找规律。

因为只有一些没有公共边的环，所以每个点的度数都是偶数。因此可以列出一系列异或方程组，注意有可能存在方程数量>未知数数量的情况，因此配合线性基进行高斯消元。

最后的答案就是 $2^{cnt}$ （$cnt$ 是自由元的个数），此外注意特判无解。

跟2020CCPC网络赛的一个毒瘤题完全一样，而且弱化了数据范围。

求最短的一段区间，该区间的异或和 $\geq k$ 。

本来是完全不会的，但是瞎搞了半天之后发现这题和USACO Cow XOR是一样的。这题要求的是异或和最大且最短的区间。思路就是我枚举右端点，对右端点查询最大且最近的左端点，然后插入当前枚举到的端点。

因此只需要对Trie树进行一下修改，记录每个子树中最右侧的左端点，然后枚举右端点即可，与Cow XOR不同的是：我们要找的左端点只需要满足异或之后 $\geq k$ ，这个可以分类讨论一下解决。

给定 $n,k$ ，已知递推公式：$a_{i+1}=(n-2)a_{i}+(n-1)a_{i-1}$ ，求第一个满足 $a_k \equiv x\pmod{998244353}$ 的 $a_k$ 的 $k$ 。

先变化一下：$a_{i+1}+a_i=(n-1)(a_{i}+a_{i-1})$ 。

然后分奇偶求出通项公式，进行一通转化之后最后可以得到一个形如 $(n-1)^{k-1}\equiv A\pmod{998244353}$ 的式子（$A$ 是一个形式比较复杂的常数），直接BSGS求方程解，时限很卡。

求一个最大面积的满足每列非递减的矩阵。

转化为01矩阵每个位置1代表该位是否比上面一位小，然后就是求最大的全1矩阵裸题了。

虽然不明白为什么有单调性，~~但是队友的二分+并查集试了一下就过了~~。

感谢Hugin场外援助，树状数组+cdq过了数据结构题。