下面是过了的题。

Indirect Sort

可以发现 \(1\) 在 \(a_1\) 处，则其他位置可以自由交换；否则 \(1\) 的对应数不能变大，也不能换到 \(a_1\) 上。所以有一组合法操作的充要条件是 \(a_1=1\)。

Maximum Substring

可以发现花费为 \(cnt_0cnt_1\) 时取整个串一定最优，其余显然是处理极长相同值的段即可。

Complementary XOR

考虑构造 \(s_1,s_2\) 对应的差分序列 \(d_1,d_2\)。此时选择区间 \([l,r]\) 进行操作后，\(d_{1,l},d_{1,r+1}\) 和 \(d_{2,1},d_{2,l},d_{2,r+1}\) 都会取反（\(d_{1,n+1},d_{2,n+1}\) 恒为 \(0\)）；而目标是将 \(d_1,d_2\) 内每个数变为 \(0\)。此时 \(\exists i>1,d_{1,i}\ne d_{2,i}\) 则无解；否则结合 \(d_{1,1},d_{2,1}\) 的初值讨论即可。

Count GCD

令 \(G_i=\gcd\limits_{j=1}^i a_i\)，考虑从 \(G_i\) 到 \(G_{i+1}\) 需要 \(a_{i+1}\) 满足什么性质。此时 \(\gcd(G_i,a_{i+1})\) 为 \(G_{i+1}\)，需要 \(G_i\bmod G_{i+1}=0\) 且 \(\frac{G_i}{G_{i+1}}\) 和 \(\frac{a_{i+1}}{G_{i+1}}\) 互质。此时可以对于每个 \(\frac{G_i}{G_{i+1}}\) 处理质因数（对于某个合法的情况，\(\prod_{i=1}^{n-1}\frac{G_i}{G_{i+1}}\le M\)，故总时间复杂度为 \(O(\sqrt m)\)），然后对于 \(\frac{a_{i+1}}{G_{i+1}}\) 容斥出对应的由于 \(2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23<10^9<2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29\)；可得单次容斥计算的时间不超过 \(O(2^9)\)。