题解 CF1174E 【Ehab and the Expected GCD Problem】

· · 题解

在我的博客食用效果更佳：点这里

一道 Div. 2 的难度 2500 的题，真的不是吹的……

首先考虑排列的第一个数 。假如分解质因子后为 \prod p_i^{c_i}，那么此时排列价值的最大值为 \sum c_i。

为什么？因为如果 \gcd 变了，那么一定变成原来 \gcd 的约数。每次变化 \sum c_i 至少 -1。所以最大值就是 \sum c_i。

那么排列的价值达到最大值，只有在第一个数的 \sum c_i 达到最大值才可能，并且每次 \gcd 变化只会令 \sum c_i 减小 1。

首先发现，质因子 p_i 中不会有 \ge 5 的数。因为此时可以把 p_i 变成 2^2，\sum c_i 更大且仍然合法。

然后，设分解质因子后 3 的次数为 c，那么 0\le c\le 1。因为当 c\ge 2 时，可以把 3^2 变成 2^3，\sum c_i 更大且仍然合法。

所以第一个数可以被表示成 2^x3^y，其中 y\in\{0,1\}。

那么就能上DP了。（为什么每次都那么突然……）

设 f[i][x][y] 表示目前填了前 i 位，当前的 \gcd 是 2^x3^y，的总合法序列数。

初始状态 f[1][\lfloor\log_2n\rfloor][0]=1。如果 2^{\lfloor\log_2n\rfloor-1}\times 3\le n，那么还有 f[1][\lfloor\log_2n\rfloor-1][1]=1。其它的状态无用，只有这两个状态的 x+y 达到了最大值。

答案为 f[n][0][0]。因为排列包含 1，所以 \gcd 一定会变为 1。

如何转移？（以下设 cnt(x)=\lfloor\frac{n}{x}\rfloor，即 x 的倍数的个数）

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1000100,mod=1000000007;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
    char ch=getchar();ll x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int n,lt,f[maxn][21][2];
inline int cnt(int x){return n/x;}
int main(){
    n=read();
    lt=log2(n);
    f[1][lt][0]=1;
    if((1<<(lt-1))*3<=n) f[1][lt-1][1]=1;
    FOR(i,2,n) FOR(j,0,lt){
        f[i][j][0]=(1ll*f[i-1][j][0]*(cnt(1<<j)-(i-1))+1ll*f[i-1][j+1][0]*(cnt(1<<j)-cnt(1<<(j+1)))+1ll*f[i-1][j][1]*(cnt(1<<j)-cnt((1<<j)*3)))%mod;
        f[i][j][1]=(1ll*f[i-1][j][1]*(cnt((1<<j)*3)-(i-1))+1ll*f[i-1][j+1][1]*(cnt((1<<j)*3)-cnt((1<<(j+1))*3)))%mod;
    }
    printf("%d\n",f[n][0][0]);
}