题目描述
题目链接
一开始怎么都没想到状压DP, 后来看了题解才想到的
题解
前置知识
为了解决本题，你应该要会
- 状压DP
- 素数筛法（打表其实也可以）
思路
状态
看到题，容易想到这是一道DP
观察题目，发现应该是以当前有没有出现某个数作为状态
即(dp[i])就表示前(i)个人可以选出的完美组合的方案数
又因为题目要求编号两两互质，所以说肯定要将当前已选的素数记录下来
所以说要使用状压DP
但我们发现题目中(n leq 3000)
(3000)以内的质数有(430)个，也就是说状态数多达(2^{430}-1)个，肯定存不下
我们该如何减少状态数呢？我们看回题目，发现一些组合中除了包含一些素数编号，还包含了另一些素数乘积的编号
那么对于一些素数来说，由于它在数内最多出现一次（即大于(sqrt{n})），
所以说我们即使直接枚举这些素数的倍数，也无需考虑倍数中出现该素数的情况
所以说我们只需要记录小于(sqrt{n})的素数即可，这样状态数最多只有(2^{16}-1)个
至此，我们的状态就定下来了，也就是dp[i][st]，
其中i表示前(i)个人可以选出的完美组合的方案数，st表示当前组合中包含的素数
预处理
首先，我们需要先求出(sqrt{n})中的素数
然后我们遍历(1-n)，对于每一个数(x)
- 如果(x)存在大于(sqrt{n})的质因子(p)，(frac{x}{p})就是(p)可取的倍数之一，那我们就将(frac{x}{p})质因数分解，并将分解得到的状态存入(p)记录倍数的数组
- 如果(x)不存在大于(sqrt{n})的质因子，那么我们就将(x)质因数分解得到的状态存入(x)记录因数的数组中
状态转移方程
我们遍历(2-n)，对于前(x)个人可以选出的的方案数
- 如果(x)是大于(sqrt{n})的质数
那么对于所有可行的倍数(k)，我们都在将与(k)互质的方案上加入(xk)，最后再加入单独的(xk)与原先的状态 - 如果(x)是大于(sqrt{n})的质数的倍数
那么因为(x)所有的倍数都已经遍历过了，所以跳过当前(x) - 如果(x)不存在大于(sqrt{n})的质因子
对于(x)质因数分解的状态(k)，对于所有与(k)互质的方案都加入(x)，最后再加入单独的(x)与原先的状态
通过观察我们可以发现，三种情况代码其实是一样的
然后我们只需要求出对于前(n)个人可以选出的的方案数的和就可以了
当然，我们还要记得对于所有方案都加入(1)，最后再加入单独的(1)与原先的状态就可以了
代码
#include<iostream>
#include<vector>
#define mod 1000000007
using namespace std;
int n;
int cnt,phi[20];
bool vis[3005];
vector<int>g[3005];
long long dp[2][70000];
int main() {
cin>>n;
for(int i=2; i<=n; i++) {
if(vis[i]==false) {
phi[cnt++]=i;
for(int j=i; j<=n; j+=i)vis[j]=true;
}
}//筛素数
for(int i=1; i<=n; i++) {
int x=i,num=0;
for(int j=0; j<cnt; j++) {
while(x%phi[j]==0) {
x=x/phi[j];
num=num|(1<<j);
}
}
if(x==1)g[i].push_back(num);//当x存在大于n的开方的质因子p
else g[x].push_back(num);//当x不存在大于n的开方的质因子p
}
dp[0][0]=1;//初始化
for(int i=2;i<=n;i++){
for(int j=0;j<g[i].size();j++){
for(int k=0;k<(1<<cnt);k++){
if(k&g[i][j])continue;//k必须与g[i][j]出现的素数不同，即互质
dp[1][k|g[i][j]]=(dp[1][k|g[i][j]]+dp[0][k])%mod;//对于原本的方案加入倍数或本身
//如今两个素数都包含
}
dp[1][g[i][j]]++;//加入它本身
}
for(int j=0;j<(1<<cnt);j++){
dp[0][j]=(dp[0][j]+dp[1][j])%mod;//加入原先的方案
dp[1][j]=0;
}
}
long long ans=0;
for(int i=0;i<(1<<cnt);i++)ans=(ans+dp[0][i])%mod;//求出总方案数
cout<<(ans*2+1)%mod;//求出包含1的方案
return 0;
}