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 () {
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(1ll*dp[i][0][0]*pp[n-i]%mod);
return 0;
}
|
近期评论