下面是过了的题。
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)\)。
标签:CF1750,frac,gcd,记录,times,此时,对应 From: https://www.cnblogs.com/Fran-CENSORED-Cwoi/p/16865387.html