My Blogs
[ARC184B] 123 Set
首先一个最基本的性质是如果 $x$ 不是 $2$ 或者 $3$ 的倍数则 $x$ 一定会被操作。基于这个简单观察，可以进一步的发现：取出所有不是 $2,3$ 的倍数的数 $x$，则对于不同的 $x$，$2^i3^jx$ 之间是没有关系的。所以可以对于不同的 $x$ 分别处理。
考虑操作了 $x$ 之后可以覆盖掉 $2x,3x$，很深刻的想法是看成一个矩形，左上角是 $x$，每向右一格 $\times 3$，每向下一格 $\times 2$。显然对于一个 $x$ 如果只保留 $\leq n$ 的表中的数，则其随着行数的增加，列数在减小。这是一个杨表，而操作一个数相当于把格子 $(i,j),(i,j+1),(i+1,j)$ 覆盖，而要求的就是用尽量少的操作数把这个杨表全都覆盖。
因为列数不会很多（最多 $19$ 列，$3^{19}>10^9$），所以可以直接轮廓线 DP，状压记录轮廓线上的每个格子是否被操作了，转移也比较简单。
如何计算最终答案？考虑计算每个杨表对应了多少个 $x$。把杨表中的数从小到大加入，设其中最大的数是 $v_i$，则其对应了 $\lfloor\frac n{v_i}\rfloor-\lfloor \frac n{v_{i+1}}\rfloor$。而不同杨表的个数显然不会太多，对每个暴力求就能过，当然也可以进行打表。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int n;
int f[2][20][1<<19];
int a[31],pw2[40],pw3[40];
inline int solve()
{
for(int i=0;i<2;++i)for(int j=0;j<=a[1];++j)
for(int k=0;k<(1<<a[1]);++k)f[i][j][k]=inf;
// for(int i=1;i<=30;++i)write(a[i]);
// puts("");
int now=1,pre=0;
f[0][0][0]=0;
for(int i=1;i<=31;++i)
{
swap(now,pre);
if(!a[i])return f[now][0][0];
for(int j=0;j<a[i];++j)
{
for(int k=0;k<(1<<a[i]);++k)
{
int lef=j?((k>>(j-1))&1):0,up=(k>>j)&1;
if(lef|up)Mmin(f[now][j+1][k&(~(1<<j))],f[now][j][k]);
Mmin(f[now][j+1][k|(1<<j)],f[now][j][k]+1);
}
}
for(int j=0;j<=a[i+1];++j)
{
for(int k=0;k<(1<<a[i+1]);++k)
f[pre][j][k]=inf;
}
int lim=(1<<a[i+1])-1;
for(int k=0;k<(1<<a[i]);++k)
Mmin(f[pre][0][k&lim],f[now][a[i]][k]);
}
assert(0);
return 0;
}
inline int get(int x){return x-x/2-x/3+x/6;}
int F[500]={
//...
};
inline void mian()
{
vt ve;
read(n);
pw2[1]=pw3[1]=1;
for(int i=2;i<=34;++i)pw2[i]=pw2[i-1]*2;
for(int i=2;i<=22;++i)pw3[i]=pw3[i-1]*3;
for(int i=1;pw2[i]<=n;++i)
{
for(int j=1;pw2[i]*pw3[j]<=n;++j)
ve.eb(tup(pw2[i]*pw3[j],i,j));
}
// exit(0);
sort(ve.begin(),ve.end(),[&](tup x,tup y){return x.x<y.x;});
ve.eb(tup(n+1,0,0));
int ans=0;
for(int i=0;i<(int)ve.size()-1;++i)
{
int tmp=get(n/ve[i].x)-get(n/ve[i+1].x);
a[ve[i].y]=ve[i].z;
//F[i]=solve()
ans+=tmp*solve();
}
write(ans);
}