「AGC039E」Pairing Points
在 \(n>1\) 时，有一个很好的性质：一条边至少要与一条边相交，不然就会有不止一个连通块。
考虑圆上 \(1\) 号点的连边将圆分割成了两半，有两种情况：
-
所有边均为二部间的连边，这是简单处理的。
-
一条边跨越二部，剩下的边均是内部的边。（如果不止一条，则会连出环）
那么有一个 dp，记 \(f(l,r,i)\) 表示编号为 \([l,r]\) 的点，\(i\) 号点对外部连边，内部连边的方案数。直接转移是 \(O(n^7)\) 的，可以优化到 \(O(n^5)\)。
「AGC036F」Square Constraints
简单题。
考虑所有 \(i\in [0,n)\) 的限制都是一个“后缀限制”，所有 \(i\in[n,n+n)\) 的限制都是前缀限制。
把其中一者容斥成另一者便可以简单 dp，时间复杂度 \(O(n^3)\)。
「AGC035E」Develop
我会 \(k=2\)。
「AGC035D」Add and Remove
数据范围很小，考虑优秀的搜索。
枚举最后一个被删除的数，他对答案贡献的系数是 \(2\)，而 \(a_1,a_n\) 对答案贡献的系数为 \(1\)。记下来两侧对答案贡献的系数，然后搜索即可。
状态数是 \(O(n^22^n)\) 的，但需要哈希表存储。直接搜是 \(O(3^n)\) 的，已经足以通过。
「AGC034F」RNG and XOR
简单题。
考虑答案的集合幂级数 \(F(x)\)，则有 \(F(x)A(x)+C(x)=F(x)\)。
其中 \(C(x)\) 是转移的系数，有 \([x^s]C(x)=1(s\neq 0)\)。
考虑三者的 \(FWT\) 数组 \(f(x),a(x),c(x)\)，有 \(f(0)a(0)+c(0)=f(0)\)，因为 \(a(0)=1\)，可以得到 \(c(0)=0\)，也就会有 \(C(0)=1-2^n\)。
\(a(x)\) 与 \(c(x)\) 可以通过 \(FWT\) 算出，对于 \(x\neq 0\)，我们可以根据 \(f(x)a(x)+c(x)=f(x)\) 计算出 \(f(x)\) 的值（此时逆元存在）。
而 \(f(0)=-\sum_{x\neq 0}f(x)\)，这是因为 \(\sum f(x)=2^n\times F(0)=0\)。
通过 \(f(x)\)，我们可以用 \(IFWT\) 还原出 \(F(x)\)。
时间复杂度 \(O(n2^n)\)。
「AGC032E」Modulo Pairing
如果没有取模的限制，那么显然是最小配最大，次小配次大这样依次匹配。而有了这个限制，我们就需要找到一个断点，使得：
-
两边均为上述匹配方式。
-
左边的取模无效，右边的取模有效。
这可以二分，时间复杂度 \(O(nlogn)\)。
「AGC030E」Less than 3
在不同数之间用“竖线”隔开，由于有连续段的限制，每次操作为将一条线左移或者右移动。这些线不能碰撞，且只能在头尾产生或被消灭。
序列相等当且仅当竖线一一对应，且奇偶性正确。
我们认为头尾初始都有无数多条线，然后枚举偏移量 \(\Delta\) 便可以 \(O(n^2)\) 求解。
这便可以通过此题，但可以更优。
将线的移动放在数轴上考虑，就会有好多个形如 \(|\Delta-k_i|\) 的式子，可以开个桶 \(O(n)\) 求解，也可以通过中位数直接算出最优的 \(\Delta\)。
标签：11,连边,限制,取模,可以,2023.5,上车,复杂度,neq From： https://www.cnblogs.com/Nesraychan/p/17392414.html