杂题集三
同余方程往互质方向考虑¶
I.六元组计数 - The 2024 Shanghai Collegiate Programming Contest - Codeforces
从问题终点反推，发现变量基本都是独立的，只需要求 \(a^{p}\bmod P\) 的信息，然后 NTT 合并一下。
从问题起点出发，可以通过原根的幂次来遍历 \(1,2,\cdots, P-1\)，把问题转化为
核心问题
对于 \(0\le i<M, 0<j\le N\)，然后对于所有 \(0\le t<M\)，求有多少组 \((i,j)\) 满足 \(i\cdot j \equiv t \pmod M\)。
其中 \(M\) 未必是素数，实际上是 \(P-1\)。
实际上这里适合 倒着 并 先假设互质性去想。
此外的操作都是很常规的解同余方程的手法：
- 先出一个有解的必要条件，一般是和模数作 gcd，无解直接排除；
- 然后可以同时约去 g，转化为一个充要条件，然后发现多了一个互质性，可以弄逆元操作。
解答
如果 \(t\) 和 \(M\) 互质，可以想到，\(j\) 如果不与 \(M\) 互质，那 \(i\) 就无解；反之，可以直接知道 \([0,M)\) 中间存在唯一解 \(i\)。
再尝试一般化。\(j\) 如果不与 \(M\) 互质则无解，实际上是利用了 \(\bmod M\) 后，与 \(M\) 的 \(\gcd\) 不变。也就是说有这样一个必要条件
所以有这样一个必要条件 \(g_1:=\gcd(j, M) | \gcd(t, M) =:g_1\cdot g'\)。 当这两个数字确定好了，我们前面的经验里直接算出了 \([0,M)\) 这样特殊的一组剩余系中有多少解，这里也试试。 $$ i \cdot g_1 \cdot \frac{j}{g_1} \equiv g_1\cdot g' \mod g_1\cdot M' $$ 希望把 \(g_1\) 约掉以求 \(\frac{j}{g_1}\) which is a integer 是一个与模数互质的数 $$ i \cdot \frac{j}{g_1} \equiv g' \mod M' $$ 于是 \(i\) 在 \(\bmod M'\) 意义下的结果又是唯一的，从而在 \([0,M)\) 这样特殊的一组剩余系中有 \(\frac{M}{M'} = g_1\) 个。
必要条件中这个整除性也给算法设计提供了遍历。
枚举复杂度就是经典的调和级数。
初始只有一个点引起的奇偶性不变量¶
想一下
00 -> 11
01 -> 10
11 -> 00
奇偶性保持不变。
这题面我最开始看错了，以为是一个正方体区域，于是知道 x 轴能确定后，y 自然确定，两个坐标唯一确定一个点。（于是造出了一个思路没有本质区别的新题）
实际上这题形状是 N 型。所以 y 轴并没有这样的不变量。但如果想象一个新坐标轴 \((x,x+y)\)，其实这个新 y 轴就有这样的不变量，回来找原 y 轴也是容易的。
不变量与服从二维势能函数的变量¶
这题像是考虑了两维的势能函数，把四种操作分了两类。
第一个势能函数是 逆序对。第一类操作每次 -2，第二类操作每次 -1。
第二个势能函数是 偶数位上 0 的数量。第一类操作不变，第二类操作每次 \(\pm 1\)。
由于初态和终态都已确定，势能之差的绝对值就能给出操作次数的下界。（先通过第二个势能函数说明第二类操作的下界，这个下界又能结合第一个势能函数推出操作总和的下界。）
如何达到这个下界？能做第一类操作就先第一类操作，直到不行，那么我们可以证明这个状态下，总存在一个方法使得第二个势能函数朝着终态的方向移动 \(1\)。如此循环即可。