526互联

CF1174E Ehab and the Expected GCD Problem 题解

发布时间 2023-08-31 21:43:22作者: User-Unauthorized

题意

对于一个排列 \(p\)，定义 \(g\) 为 \(p\) 的前缀最大公约数序列，即 \(g_i = \gcd\limits_{j = 1}^{i} p_j\)。定义 \(f(p)\) 为 \(g\) 的元素种类数。

给定 \(n\)，求长度为 \(n\) 的且使得 \(f(p)\) 取最大值的排列个数，对 \(10^9 + 7\) 取模。

（\(1 \le n \le 10^6\)）。

题解

考虑转化限制条件，定义满足要求的排列的第一个元素为 \(s\)。因为 \(s\) 和任何数的最大公约数一定不大于 \(x\)，所以有前缀最大公约数序列单调递减。又有递减的过程中每次递减一定是除去当前元素的一个质因子，考虑上元素种类数最大的限制，所以每次除去的一定是质因子。故符合要求的 \(s\)，一定是 \(\left[1, n\right]\) 中质因子最多的数。

首先发现 \(2^{\left\lfloor\log_2 n\right\rfloor}\) 一定是符合要求的 \(s\)，因为不会存在质因子数目多于 \({\left\lfloor\log_2 n\right\rfloor}\) 的数。对于其他的可能，考虑替换其中的质因子 \(2\)，如果替换了一个大于等于 \(4\) 的质因子，那么其质因子数目一定减少，不符合要求，故只能替换质因子 \(3\)。考虑可以替换的数量，替换 \(1\) 个显然合法，如果替换了 \(\ge 2\) 个，那么显然有 \(2^3 < 3^2\)，所以这种情况的质因子数也会减少，不符合要求。

综上，符合要求的 \(s\) 一定有 \(2^{\left\lfloor\log_2 n\right\rfloor}\)，若 \(2^{\left\lfloor\log_2 n\right\rfloor - 1} \cdot 3 \le n\)，那么 \(2^{\left\lfloor\log_2 n\right\rfloor - 1} \cdot 3\) 也符合要求。即符合要求的 \(s\) 可以表达为 \(2^x \cdot 3^y\) 的形式，其中 \(y \in \left\{0, 1\right\}\)。

考虑使用 \(\text{DP}\)，定义 \(f_{i, x, y}\) 为取了 \(i\) 个数，且当前最大公约数为 \(2^x \cdot 3^y\) 的方案数。对于合法的 \(s = 2^x \cdot 3^y\)，有 \(f_{1, x, y}\) 初始值为 \(1\)，反之为 \(0\)。转移考虑最大公约数的变化情况。

最大公约数未改变

有转移

\[\begin{aligned} f_{i, x, y} \leftarrow f_{i - 1, x, y} \times \operatorname{count}\left(2^x \cdot 3^y\right) \end{aligned}\]

最大公约数除去质因子 \(2\)

有转移

\[\begin{aligned} f_{i, x, y} \leftarrow f_{i - 1, x + 1, y} \times \left(\operatorname{count}\left(2^x \cdot 3^y\right) - \operatorname{count}\left(2^{x + 1} \cdot 3^y\right)\right) \end{aligned}\]

最大公约数除去质因子 \(3\)

有转移

\[\begin{aligned} f_{i, x, 0} \leftarrow f_{i - 1, x, 1} \times \left(\operatorname{count}\left(2^x\right) - \operatorname{count}\left(2^{x} \cdot 3\right)\right) \end{aligned}\]

其中 \(\operatorname{count}(x) = \sum\limits_{i = 1}^{n} \left[x \mid i\right]\)，即 \(\left[1, n\right]\) 中 \(x\) 的倍数个数。最终答案即为 \(f_{n, 0, 0}\)。

总复杂度 \(\mathcal{O}(n \log n)\)，可以通过本题。

Code

//Codeforces - 1174E
#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;

typedef std::array<valueType, 2> Data;
typedef std::vector<Data> DataVector;
typedef std::vector<DataVector> DataMatrix;

constexpr valueType MOD = 1e9 + 7;


#define ModOperSafeModOption false

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % mod;
}

int main() {
    valueType N;

    std::cin >> N;

    auto const count = [N](valueType x) {
        return N / x;
    };

    auto const G = [](valueType i2, valueType i3) {
        return (1 << i2) * (i3 == 1 ? 3 : 1);
    };

    valueType M = std::floor(std::log2((long double) N));

    DataMatrix F(N + 1, DataVector(M + 1));

    F[1][M][0] = 1;

    if ((1 << (M - 1)) * 3 <= N)
        F[1][M - 1][1] = 1;

    for (valueType j = M - 1; j >= 0; --j) {
        for (valueType i = 2; i <= N; ++i) {
            Inc(F[i][j][0], mul(F[i - 1][j][0], count(G(j, 0)) - (i - 1)));
            Inc(F[i][j][1], mul(F[i - 1][j][1], count(G(j, 1)) - (i - 1)));

            Inc(F[i][j][0], mul(F[i - 1][j + 1][0], count(G(j, 0)) - count(G(j + 1, 0))));
            Inc(F[i][j][1], mul(F[i - 1][j + 1][1], count(G(j, 1)) - count(G(j + 1, 1))));

            Inc(F[i][j][0], mul(F[i - 1][j][1], count(G(j, 0)) - count(G(j, 1))));
        }
    }

    std::cout << F[N][0][0] << std::endl;

    return 0;
}