P5856「SWTR-03」Game(状压DP)
nofind
·
·
题解
题意
我自闭了，连蓝题都不会了，还得看题解。
以下是我理解的官方做法，献给给广大没看懂官方题解的神仙们。作者蒟蒻，如果有什么不对的地方请指出。
观察题目的限制，发现q是一个p^z的形式，因此我们可以考虑每个质数p。
对于每个质数p，我们求出一个0-1串state_i，其中第i位为1则表示存在一个数，它分解后p这个质因子的次幂为i。特殊地，如果一个数不含p这个质因子，那么第0位为1。p的次幂的上界很小，p=2时最大，才\log_2级别，因此是开得下的。
现在我们考虑通过题中的操作使得a_{1...n}相同的过程：
对于每个质数p，显然只有所有a_i分解后的p的次幂相同才会满足条件。
先假设我们要将所有的a_i中p的次幂都消成0。
此时，我们要对p的状态求出一个最小的集合，满足将这个集合内的数任意相加可以拼出p的状态中所有的位置。
就拿官方题解里的例子吧：
对于1000111010，在1,3,4,5,9位上是1（注意我们是从右向左从零开始数的），于是f_{(1000111010)_2}=3，因为我们可以通过\{1,3,5\}拼出所有的数。（1=1，3=3，4=1+3，5=5，9=1+3+5）
此时我们在q=p^1时操作分解后p的次幂为1,4,9的位置，在q=p^3时操作分解后p的次幂为3,4,9的位置，在q=p^5时操作分解后p的次幂为5,9的位置，那么所有的数中p的次幂都为0。
那么我们就设f_s表示状态s的答案，我们可以dfs求出。
但是包含s的状态t（即s是t的子集）的答案f_t也可以更新f_s（能拼出t就能拼出s），我们再枚举每个状态，更新它的子集即可。
现在考虑我们不把所有的a_i中的p的次幂消成0的情况。
这时候需要满足该状态最低位（即第0位）不为0，因为为0的话就说明有一个数根本就没有p这个质因子，那肯定要全消完。
那么我们保留p^k就相当于s_p>>k这个状态的答案，还是拿之前的那个举例：
我们现在保留$p^1$，也就是我们要找最小的集合，使其能拼成$0,2,3,4,8$，那么对应的状态就是$s_p>>1$。
由衷地感叹：这题的确是道思维好题。
code（真·抄的官方题解）：
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int maxm=20;
int n,ans;
int a[maxn],f[1<<maxm],state[1<<maxm],cnt[1<<maxm];
bool vis[maxn];
vector<int>prime;
inline void pre_work()
{
vis[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!vis[i])prime.push_back(i);
for(unsigned int j=0;j<prime.size()&&i*prime[j]<=1000000;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
void dfs(int dep,int now,int s)
{
f[s]=min(f[s],dep-1);
if(dep>5)return;
for(int i=now;i<=20;i++)dfs(dep+1,i,(s|(s<<i))&((1<<20)-1));
}
int main()
{
pre_work();
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
memset(f,0x3f,sizeof(f));
dfs(1,1,1);
for(int s=(1<<20)-1;s;s--)
for(int j=1;j<=20;j++)
if(!((s>>(j-1))&1))f[s]=min(f[s],f[s|(1<<(j-1))]);
for(int s=1;s<(1<<20);s++)if(!(s&1))f[s]=min(f[s],f[s>>1]);
for(int i=1;i<=n;i++)
{
int tmp=a[i];
for(unsigned int j=0;j<prime.size()&&prime[j]*prime[j]<=tmp;j++)
{
if(tmp%prime[j])continue;
int k=0;
while(tmp%prime[j]==0)k++,tmp/=prime[j];
state[prime[j]]|=1<<k;cnt[prime[j]]++;
}
if(tmp>1)cnt[tmp]++,state[tmp]|=2;
}
for(int i=2;i<=1000000;i++)
{
if(cnt[i]!=n)state[i]|=1;
ans+=f[state[i]];
}
printf("%d",ans);
return 0;
}
```