AtCoder Grand Contest 036 题解
A - Triangle
题意
构造三角形满足：
- 顶点坐标为整数，且在 \(0\) 到 \(10^9\) 之间。
- 面积为 \(\frac{S}{2}\)。
\(S\le 10^{18}\)
题解
可以令其中一个点 \(A\) 在原点，另外两点分别在 \(B(x_1,y_1)\) 和 \(C(x_2,y_2)\)，不妨令 \(C\) 在 \(B\) 的逆时针方向，那么有 \[\overrightarrow{AB}\times \overrightarrow{AC}=S\]
其中 \(\times\) 表示向量的叉积。代入 \(x_1,y_1,x_2,y_2\) 得到 \[x_1y_2-x_2y_1=S\]
我们可以将 \(S\) 表示成 \(10^9a-b\) 的形式，其中 \(0\le a,b\le 10^9\)。于是令 \(x_1=10^9,y_2=a,x_2=1,y_1=b\) 即可。
B - Do Not Duplicate
题意
给定一个序列 \(A_0,A_1,\ldots,A_{N-1}\)，将该序列复制 \(K\) 份得到序列 \(X_0,X_1,\ldots,X_{NK-1}\)。
有一个初始为空的序列 \(s\)，按 \(i\) 从 \(0\) 到 \(NK-1\) 的顺序，依次执行以下操作：
- 若 \(s\) 中不包含 \(X_i\)，则在 \(s\) 的末尾加入 \(X_i\)。
- 否则，则不断删去 \(s\) 的末尾元素，直到 \(s\) 中不包含 \(X_i\)。此时不加入 \(X_i\)。
求最终得到的序列 \(s\)。
\(N\le 2\times 10^5,K\le 10^{12}\)
题解
假设我们现在需要加入 \(X_p,\ldots,X_{NK-1}\)，且 \(s\) 序列当前为空。我们令 \(q\) 为第一个满足 \(X_q=X_p\) 且 \(q > p\) 的数。
若 \(q\) 存在，那么在加入 \(X_q\) 时一定会把 \(s\) 序列清空，所以我们可以直接递归操作 \(X_{q+1},\ldots,X_{NK-1}\)，即执行 \(p\gets q+1\)。
否则若 \(p\) 不存在，由于 \(X\) 是 \(N\) 个数复制若干份得到的，那么剩余部分的长度一定不超过 \(N\)，直接暴力模拟即可。
于是我们只要处理第一部分不断跳 \(p\) 的过程。注意到 \(p\bmod N\) 的值会形成一个环，每次跳一步 \(K\) 可能会减少 \(0,1,2\)，这只需要将 \(K\) 对每次跳一个环会减少的值取模，最后再在环上跳若干步即可。
时间复杂度 \(O(N+\max A_i)\) 或 \(O(N\log N)\)。
C - GP 2
题意
有一个长度为 \(N\) 个序列 \(x_0,x_1,\ldots,x_{N-1}\)，初始都为 \(0\)。你需要求执行恰好 \(M\) 次以下操作后能得到多少不同的序列：
- 选择两个整数 \(i,j\ (0\le i,j < N,i\ne j)\)，将 \(x_i\) 加 \(2\)，将 \(x_j\) 加 \(1\)。
对 \(998244353\) 取模。
\(N\le 10^6,M\le 5\times 10^5\)
题解
一个序列合法的充要条件是：
- \(\forall 0\le i < N,0\le x_i\le 2M\)
- \(\sum\limits_{i=0}^{N-1}x_i=3M\)
- \(x_i\) 是奇数的 \(i\) 的数量不超过 \(M\)。
必要性显然，充分性可以考虑归纳证明，不再展开。
于是我们可以枚举奇数的数量 \(d\)，将所有奇数都减 \(1\)，再将所有数除以 \(2\)，就变成了一个经典的求不定方程整数解数量的问题。即，\(N\) 个整数变量，和为 \(\frac{3M-d}{2}\)，其中 \(d\) 个变量的范围为 \(0\le x_i < M\)，\(N-d\) 个变量范围为 \(0\le x_i \le M\)。可以套用经典的容斥和隔板法的解法，即枚举哪些变量不满足上界的限制，可以得到答案为 \[ \sum_{i=0}^{d}\sum_{j=0}^{n-d}(-1)^{i+j}\binom{d}{i}\binom{n-d}{j}\binom{\frac{3M-d}{2}-iM-j(M+1)+N-1}{N-1} \]
由于 \(i,j\) 需要满足 \(iM+j(M+1)\le \frac{3M-d}{2}\)，合法的 \(i,j\) 只有常数个，所以总时间复杂度为 \(O(N+M)\)。
D - Negative Cycle
题意
有一张 \(N\) 个点的图，边的状态为：
- 对于所有 \(0\le i < N-1\)，\(i\) 向 \(i+1\) 有一条边权为 \(0\) 的不可被删除的有向边。
- 对于所有 \(0\le i < j < N\)，\(i\) 向 \(j\) 有一条边权为 \(-1\) 的可以用 \(A_{i,j}\) 的代价删除的有向边。
- 对于所有 \(0\le j < i < N\)，\(i\) 向 \(j\) 有一条边权为 \(1\) 的可以用 \(A_{i,j}\) 的代价删除的有向边。
求使得图没有负环（即边权和为负数的环）的最小代价。
\(N\le 500\)
题解
首先我们可以把问题转化为一个差分约束的模型，即有 \(N\) 个变量，需要满足以下限制：
- \(\forall 0\le i < N-1, x_i\ge x_{i+1}\)
- \(\forall 0\le i < j < N, x_j-x_i\le -1\)
- \(\forall 0\le j < i < N, x_j-x_i\le 1\)
我们需要删除后面两种限制中的一些限制使得问题有解。
满足第一条限制的 \(x\) 一定是 \(d,d,\ldots,d,d-1,\ldots,d-1,d-2,\ldots,d-2,\ldots\) 的形式。\(x\) 相同的连续段中两两之间的 \(-1\) 的边需要删去，而 \(x\) 相差超过 \(1\) 的两个连续段之间的 \(+1\) 边都需要删去。
考虑 DP，用 \(f_{i,j}\) 表示最后一段相同的连续段为 \((j,i]\) 时最少所需代价，转移时枚举下一段的结尾，用二维前缀和优化计算代价即可。
时间复杂度 \(O(N^3)\)。
E - ABC String
题意
有一个只包含 A、B、C 的字符串 \(S\)，求出 \(S\) 的一个最长的子序列 \(x\) 满足：
- 相邻两个字符不同；
A、B、C出现次数相同。
构造一个方案。
\(|S|\le 10^6\)
题解
首先可以把极长的相同字符的连续段缩成一个字符。
设 A,B,C 数量为 \(cnt_A,cnt_B,cnt_C\)，不妨假设 \(cnt_A\le cnt_B\le cnt_C\)。
由于最后需要使得 \(cnt_A=cnt_B=cnt_C\)，我们先尽量删 C 使得 \(cnt_C=cnt_B\)。
考虑贪心地删，那么一定是优先删除两边字符不同的 C，这样一定对答案没有影响。
若删完这些 C 后，仍然 \(cnt_C > cnt_B\)，那么考虑两边字符相同的情况。若两边字符是 B，那么删除 C 会连带删除一个 B，不会对 \(cnt_C-cnt_B\) 产生影响；若两边字符是 A，则删除 C 会连带删除一个 A。
若删完后仍然 \(cnt_C > cnt_B\)，那么一定无解。否则现在有 \(cnt_C=cnt_B\ge cnt_A\)。我们需要同时删除 B 和 C 使得 \(cnt_A=cnt_B=cnt_C\)。
注意到一个连续的 BC 或 CB 若两边不同时是 A，那么一定可以删除。发现将可以删除的 BC 或 CB 删除后一定会变成形如 ABCACBABCABCA 的形式，一定有 \(cnt_A > cnt_B\)，所以在中间删除的过程中一定会有一个时刻使得 \(cnt_A=cnt_B=cnt_C\)。
可以用链表维护，也可以每次删除后重构，时间复杂度 \(O(|S|)\)。
F - Square Constraints
题意
求满足以下条件的 \(0\) 到 \(2N-1\) 的排列 \(P_0,P_1,\ldots,P_{2N-1}\) 的数量：
- \(\forall 0\le i < 2N,N^2\le i^2+P_i^2\le (2N)^2\)
对给定的模数 \(M\) 取模，不一定为质数。
\(N\le 250,M\le 10^9\)
题解
注意到题目相当于对排列的每个位置有一个 \((l_i,r_i]\) 的限制。
没有 \(l_i\) 的限制时，我们只需要按 \(r_i\) 从小到大填数即可。
有 \(l_i\) 的限制时，考虑容斥。注意到后 \(N\) 个位置的 \(l_i=0\)，可以不考虑。将前 \(N\) 个数的 \(l_i,r_i\) 和后 \(N\) 个位置的 \(r_i\) 共 \(3N\) 个数从小到大排序，注意到最后 \(N\) 个数一定是前 \(N\) 个数的 \(r_i\)，且一定是 \(r_{N-1},r_{N-2},\ldots,r_0\)。
那么考虑枚举强制小于等于 \(l_i\) 的数的数量 \(k\)，那么前 \(2N\) 个数共选择了 \(N+k\) 个数。这个个数是确定的，于是可以 DP。
令 \(f_{i,j}\) 表示前 \(i\) 个数中，有 \(j\) 个数强制不合法时的方案数。
若当前数是后 \(N\) 个位置的上界，那么直接乘上贡献即可。
否则考虑该数是否强制不合法，两种情况都可以方便地计算贡献。
具体贡献式子可以参考代码。时间复杂度 \(O(N^3)\)。
