Ehab and the Expected GCD Problem
题目描述
\(p\) 是一个排列，定义 \(f(p)\) ： 设 \(g_i\) 为 \(p_1, p_2, \cdots, p_i\) 的最大公因数（即前缀最大公因数），则 \(f(p)\) 为 \(g_1,g_2,\cdots,g_n\) 中不同的数的个数。
设 \(f_{max}(n)\) 为 \(1,2,\cdots,n\) 的所有排列 \(p\) 中 \(f(p)\) 的最大值，你需要求有多少 \(1,2,\cdots,n\) 的排列 \(p\) 满足 \(f(p)=f_{max}(n)\)，答案对 \(10^9+7\) 取模。
Solution
考虑第一个数为 \(x\)，那么为了使得不同的数的个数最多，将 \(x\) 进行质因数分解，每次一定只能将指数 \(-1\)，否则一定不优。为了使得减的次数最多，那么 \(x\) 一定是由 \(2^a\times 3^b(b\in\{0,1\})\) 构成，因为如果出现 \(5\) 或 \(3^2\) 都可以变成 \(2^2\)。
考虑 DP 这一个前缀 \(\gcd\)。设 \(f(i,j,k)\) 表示当前在位置 \(i\)，前缀 \(\gcd\) 为 \(2^j\times 3^k\) 的方案数。记 \(g(x)=\lfloor\dfrac n x\rfloor\) 表示 \(n\) 以内 \(x\) 的倍数的个数。那么有转移：
- \(\gcd\) 不变，那么 \(f(i,j,k)\gets f(i-1,j,k)\cdot(g(2^j\times 3^k)-(i-1))\)。
- \(\gcd\) 中 \(2\) 的指数 \(-1\)，那么 \(f(i,j,k)\gets f(i-1,j+1,k)\cdot(g(2^j\times 3^k)-g(2^{j+1}\times 3^k))\)。
- \(\gcd\) 中 \(3\) 的指数 \(-1\)，那么 \(f(i,j,k)\gets f(i-1,j,k+1)\cdot(g(2^j\times 3^k)-g(2^j\times 3^{k+1}))\)。
时间复杂度 \(\mathcal O(n\log n)\)。
Code
int N, lst = 0, cur = 1;
mint f[2][21][2];
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
int lg = __lg(N);
f[cur][lg][0] = 1;
if ((1 << (lg - 1)) * 3 <= N)
f[cur][lg-1][1] = 1;
For(i, 2, N) {
swap(cur, lst);
For(j, 0, lg) f[cur][j][0] = f[cur][j][1] = 0;
For(j, 0, lg) {
f[cur][j][0] += f[lst][j][0] * (N / (1 << j) - i + 1);
f[cur][j][0] += f[lst][j+1][0] * (N / (1 << j) - N / (1 << (j + 1)));
f[cur][j][0] += f[lst][j][1] * (N / (1 << j) - N / ((1 << j) * 3));
f[cur][j][1] += f[lst][j][1] * (N / ((1 << j) * 3) - i + 1);
f[cur][j][1] += f[lst][j+1][1] * (N / ((1 << j) * 3) - N / ((1 << (j + 1)) * 3));
}
}
cout << f[cur][0][0] << '\n';
}