CF-1174E

Posted on | Edited on | In | Views:

Ehab and the Expected GCD Problem

题意

定义 $f(p)$ 表示 一个排列 $p$ 的 $g_1,g_2 \cdots g_n$ 的种类数, $g_i$ 表示该排列前 $i $ 个数的 $gcd$

$f_{max}(n)$ 表示 $n$ 的排列的最大 $f$ 值

给 $n$ 求 $f(p)=f_{max}(n)$ 的方案数

题解

显然 要让 $f$ 最大, 排列的第一个数为 $2^k$ 或 $2^{k-1}3$ , 设 $dp[i][x][t]$ 表示前 $i$ 个数的 $gcd$ 为 $\large 2^{x} 3^y$ 的方案数

$f[x][y]$ 表示 $\Large \lfloor \frac n {2^x*3^y}\rfloor$ , 答案为 $dp[n][0][0]$

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int dp[N][21][3];
int n;
int f[21][3];
int pp[N];
int main() {
    in(n);
    ll pre=1;
    for1(i,N){
        pre=pre*i%mod;
        pp[i]=pre;
    }
    for0(i,21)
    for0(j,3){
        f[i][j]=n/((1<<i)*pow(3,j));
    }
    if(n<4){
        if(n==2)puts("1");
        else if(n==3)puts("4");
        return 0;
    }
    int k=0,tn=n;
    while(tn){
        tn/=2;
        k++;
    }
    k--;
    dp[1][k][0]=1;
    if((1<<(k-1))*3<=n)dp[1][k-1][1]=1;
    itn  i,cnt;
    for(i=2;i<=n;i++){
        itn x,y;
        cnt=0;
        for0(j,k){
            x=j;
            y=0;
            dp[i][x][y]=(1ll*dp[i-1][x][y]*max(f[x][y]-i+1,0)%mod+1ll*dp[i-1][x+1][y]*(f[x][y]-f[x+1][y])%mod+1ll*dp[i-1][x][y+1]*(f[x][y]-f[x][y+1])%mod)%mod;
            if(dp[i][x][y])cnt++;
            y=1;
            dp[i][x][y]=(1ll*dp[i-1][x][y]*max(f[x][y]-i+1,0)%mod+1ll*dp[i-1][x+1][y]*(f[x][y]-f[x+1][y])%mod+1ll*dp[i-1][x][y+1]*(f[x][y]-f[x][y+1])%mod)%mod;
            if(dp[i][x][y])cnt++;
        }
        if(dp[i][0][0]&&cnt==1)break;
    }
    // outln(i);
    outln(1ll*dp[i][0][0]*pp[n-i]%mod);
    return 0;
}