闲来无事，整了一场virtual codeforces来看看手有没有变生。感觉基本的手感还是有一些的？
A. Permutation Counting
题目大意
给定 \(a_1\) 个 1, \(a_2\) 个 2, \(\ldots\) \(a_n\) 个 \(n\)，同时还能补至多\(k\)个任意数，然后把这些数排成一个数列，问这个数列最多可以有多少个子串是\({1, 2, \ldots, n}\)的排列。
思路
题目的样例给了很强的提示。显然，假设1到\(n\)的数量是递增的，那么我们可以排这么一个数列出来：
\(n-2,n-1,n,1,2,3,\ldots,n,1,2,3,\ldots,n,\ldots,1,2,3,\ldots,n\)
答案就是\(n(t-1) + 1 + p\)，其中\(t\)为出现最少的数出现的次数，\(p\)为出现多于\(t\)此的数的数量。
二分\(t\)，计算\(p\)即可。
B1. Reverse Card (Easy Version)
题目大意
计算
\[\sum_{1\le a\le n, 1\le b \le m} [(a + b) | b \cdot \mathrm{gcd}(a, b)] \]思路
显然，若\(\mathrm{gcd}(a, b) = 1\)且\(b \neq 1\), 则\(a + b \nmid b\cdot\mathrm{gcd}(a, b) \).
若\(b = 1\), 则有\(a + b | 1\)恒成立。
考虑\(b > 1, \mathrm{gcd}(a, b) > 1\), \(a + b | b \cdot \mathrm{gcd}(a, b) \Rightarrow a + b | b \Rightarrow a | b \Rightarrow \mathrm{gcd}(a, b) = b\)
原题变成
\[\sum_{1\le a\le n, 1\le b \le m} [(a + b) | b^2] \]令\(a = b(kb - 1)\)，原题变成：
\[\sum_{1\le k\le \left\lfloor \frac{(n+b)}{b^2} \right\rfloor, 1\le b \le m} 1 = \sum_{1\le b \le m} \left\lfloor \frac{(n+b)}{b^2} \right\rfloor - 1\]B2. Reverse Card (Hard Version)
\[\sum_{1\le a\le n, 1\le b \le m} [b \cdot \mathrm{gcd}(a, b) | (a + b)] \]思路
令\(g = \mathrm{gcd}(a, b), a = kg, b = lg, \mathrm{gcd}(k, l) = 1\)
题目变为
\[\sum_g \sum_{1\le k\le \left\lfloor \frac{n}{g} \right\rfloor, 1\le l \le \left\lfloor \frac{m}{g} \right\rfloor} [kg^2 | g(k + l)][\mathrm{gcd}(k,l) = 1]\] \[= \sum_g \sum_{1\le k\le \left\lfloor \frac{n}{g} \right\rfloor, 1\le l \le \left\lfloor \frac{m}{g} \right\rfloor} [kg | (k + l)][\mathrm{gcd}(k,l) = 1]\] \[= \sum_g \sum_{1\le k\le \left\lfloor \frac{n}{g} \right\rfloor, 1\le l \le \left\lfloor \frac{m}{g} \right\rfloor} [g | (k + l)][\mathrm{gcd}(k,l) = 1]\]考虑\(g\)的因数\(h\)，注意到，如果\(\mathrm{gcd}(k,l) = h\)，那么有\(g | (\frac{k}{h} + \frac{l}{h})\)，记\(k' = \frac{k}{h}, l' = \frac{l}{h}\)，那么原式可以变为：
\[\sum_{1 < g < \min(n, m)} \sum_h \left( [g|h] \sum_{1\le k'\le \left\lfloor \frac{n}{g} \right\rfloor} \left[\mathrm{gcd}(k',h - k') = 1\right]\cdot\left[1 \le h - k' \le \frac{m}{g}\right]\right)\]如果依此式计算,令\(\min(n, m) = N\)，得到复杂度为：
\[\sum_{1 < g < N} \sum_{h \le \sqrt{g}}\sum_{1\le k'\le \left\lfloor \frac{n}{g} \right\rfloor} O(\mathrm{gcd}) = O(N \sqrt{N} (\log N)^2)\]在\(N \sim 2\times 10^6\)时，复杂度不可接受。
如果令\(g = g'h\), 则原式化为
\[\sum_h \sum_{1 < g' < \left\lfloor\frac{\min(n, m)}{h}\right\rfloor} \sum_{1\le k'\le \left\lfloor \frac{n}{g} \right\rfloor} \left[\mathrm{gcd}(k',h - k') = 1\right]\cdot\left[1 \le h - k' \le \frac{m}{g}\right]\]注意到，若令\(\min(n, m) = N\)
\[\sum_h \sum_{1 < g' < \left\lfloor\frac{\min(n, m)}{h}\right\rfloor} \sum_{1\le k'\le \left\lfloor \frac{n}{hg'} \right\rfloor} O(\mathrm{gcd}) = O(N(\log N)^3)\]因此此时复杂度是可以接受的，依上式暴力计算即可。
花絮
第一次做的时候没想到最后一步，一直TLE，上perf看热点发现对于样例，有
1|long long sol() {
1| long long n, m, ans = 0;
1| cin >> n >> m;
|
1| long long mimn = min(m, n);
|
1.00M| for (long long g = 2; g <= mimn; g++) {
999k| long long mxk = n / g;
999k| long long mxl = m / g;
|
999k| if (mxk >= g && mxl >= g) {
999| ans += g - 1;
999| continue;
999| }
|
667M| for (long long rg = 1; rg * rg <= g; rg++) {
666M| if (g % rg != 0) {
659M| continue;
659M| }
6.98M| long long gg = g / rg;
6.98M| long long tans = gg;
9.86M| for (long long k = max(gg - mxl, 1ll); k <= mxk && k < gg; k++) {
2.88M| long long l = gg - k;
2.88M| if (l <= mxl && gcd(k, l) == 1) {
1.76M| long long a = k * g;
1.76M| long long b = l * g;
1.76M| ans++;
1.76M| }
2.88M| }
6.98M| if (gg != rg) {
12.1M| for (long long k = max(rg - mxl, 1ll); k <= mxk && k < rg; k++) {
5.21M| long long l = rg - k;
5.21M| if (l <= mxl && gcd(k, l) == 1) {
3.67M| long long a = k * g;
3.67M| long long b = l * g;
3.67M| ans++;
3.67M| }
5.21M| }
6.98M| }
6.98M| }
999k| }
|
1| return ans;
1|}
看到
667M| for (long long rg = 1; rg * rg <= g; rg++) {
666M| if (g % rg != 0) {
659M| continue;
659M| }
恍然大悟。
还是因为手生了。