题解 CF1174E Ehab and the Expected GCD Problem

发表于 分类于 阅读次数： Valine： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

毒瘤 dp 题。

首先显然可以莽一波结论。

可以发现，当排列的第一个数 a1=∏pici,pi is primea_1=\prod p_i^{c_i},p_i\ \text{is prime} 时，题目中所求排列的权值最大值为 ∑ci\sum c_i。

这是因为在第二个数及以后，前缀 gcd⁡\gcd 只会减小，不会增加，而且最好的情况是每次减小一个质因子。可以证明只要有一个确定的第一个数，该最好情况一定可以实现。

那么我们可以考虑找出使 ∑ci\sum c_i 最大的一个数 a1a_1。

再来猜一波：这个 a1a_1 的可能性不会太多，它的质因子得小。因为如果有比较大的质因子的话，它的指数 cic_i 就会被压榨，会比质因子更小的情况劣。

那么质因子得有多小呢？我们先猜：这个 a1=2xa_1=2^x。

这种情况确实很优，但不久后我们还会发现，2x⋅3y2^x\cdot 3^y 似乎也很可以。

但是到 2x⋅322^x\cdot 3^2 之后就爆炸了，因为有一个比它小但质因数分解后的指数和比它大的数 2x+32^{x+3}。

因此，质因子 33 的次数不能大于 11。

那么能不能有比 33 大的质因子呢？显然不能。因为 5>225>2^2，用了 55 及以上的不如用一堆 22 来代替。

那么我们可以得出结论：a1a_1 只能等于 22 的若干次方，或者 22 的若干次方乘上 33。

那么就可以愉快设 dp 状态了：令 fi,j,kf_{i,j,k} 表示到了该排列的第 ii 个数，当前前缀 gcd⁡=2j⋅3k\gcd=2^j\cdot 3^k 时，有多少种情况。

转移可以分三类讨论：

  • 若加入一个数后 gcd⁡\gcd 不变，那么 fi+1,j,kf_{i+1,j,k} 需要加上 fi,j,k⋅(⌊n2j⋅3k⌋−i)f_{i,j,k}\cdot\left(\left\lfloor\frac{n}{2^j\cdot 3^k}\right\rfloor-i\right)。因为 gcd⁡\gcd 不变，那么加入的数一定是当前 gcd⁡\gcd 的倍数，需要注意前面的所有数一定都是当前 gcd⁡\gcd 的倍数，不可以选已经选过的数，于是情况数需要 −i-i。
  • 若加入一个数后 gcd⁡\gcd 变少了 22 倍，那么 fi+1,j−1,kf_{i+1,j-1,k} 需要加上 fi,j,k⋅(⌊n2j−1⋅3k⌋−⌊n2j⋅3k⌋)f_{i,j,k}\cdot\left(\left\lfloor\frac{n}{2^{j-1}\cdot 3^k}\right\rfloor-\left\lfloor\frac{n}{2^{j}\cdot 3^k}\right\rfloor\right)。由于 gcd⁡\gcd 变少两倍，那么新加入的数一定得是 gcd⁡2\frac{\gcd}{2} 的倍数，但它不能是 gcd⁡\gcd 本身的倍数，因为这样的话 gcd⁡\gcd 就不会改变了。而在 gcd⁡2\frac{\gcd}{2} 的倍数和 gcd⁡\gcd 本身的倍数中，都考虑了一遍已经加入过的数，抵消掉了，因此不会加入重复的数。
  • 若加入一个数后 gcd⁡\gcd 变少 33 被，那么 fi+1,j,k−1f_{i+1,j,k-1} 需要加上 fi,j,k⋅(⌊n2j⋅3k−1⌋−⌊n2j⋅3k⌋)f_{i,j,k}\cdot\left(\left\lfloor\frac{n}{2^{j}\cdot 3^{k-1}}\right\rfloor-\left\lfloor\frac{n}{2^{j}\cdot 3^k}\right\rfloor\right)。由于 gcd⁡\gcd 变少两倍，那么新加入的数一定得是 gcd⁡3\frac{\gcd}{3} 的倍数，但它不能是 gcd⁡\gcd 本身的倍数。类似地，在 gcd⁡3\frac{\gcd}{3} 的倍数和 gcd⁡\gcd 本身的倍数中，也抵消掉了重复的数。因此这么干是对的。

代码实现上因为 33 只有可能是 00 次方或 11 次方，可以用三目运算符判断更加方便。

PS：这题十分卡常，还卡 long long 数组（如果 dp 数组用 long long 的话会炸）的空间。我是用火车头 ++ C++17 才过的（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 代码就不放火车头了
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int mod=1e9+7;
int n;
int dp[1000005][21][3];
int qaq(int x,int y) {
    return (1<<x)*(y?3:1)%mod;
}
int main() {
    scanf("%d",&n);
    int hav3=log2(n/3)+1;
    int nhav3=log2(n);
    dp[1][nhav3][0]=1;
    if(hav3==nhav3) dp[1][nhav3-1][1]=1;
    rep(i,1,n-1) {
        rep(j,0,nhav3) {
            rep(k,0,1) {
                dp[i+1][j][k]=1ll*(1ll*dp[i+1][j][k]+dp[i][j][k]*(1ll*n/qaq(j,k)%mod-i+mod)%mod+mod)%mod;
                if(j>0) dp[i+1][j-1][k]=1ll*(1ll*dp[i+1][j-1][k]+dp[i][j][k]*(1ll*n/qaq(j-1,k)%mod-n/qaq(j,k)%mod)%mod+mod)%mod;
                if(k>0) dp[i+1][j][k-1]=1ll*(1ll*dp[i+1][j][k-1]+dp[i][j][k]*(1ll*n/qaq(j,k-1)%mod-n/qaq(j,k)%mod)%mod+mod)%mod;
            }
        }
    }
    printf("%d\n",dp[n][0][0]);
    return 0;
}