目录
显示
题目链接
https://www.luogu.com.cn/problem/P2150
题解
注意到我们的可用集合只与用到的质因子有关，因此我们可以以用到的质因子为状态进行转移。
设 \(f(p,q)\) 为第一个集合的质因子状态为 \(p\)，第二个质因子的状态为 \(q\) 时的方案数，转移时要求 \(p\) 和 \(q\) 无交集即可。
然而 \(n \leq 500\) 的时候质因子数量很多，压缩起来空间不够。
注意到一个数 \(x\) 的质因数满足这样的性质：大于等于 \(\sqrt x\) 的质因子最多只有一个。这意味着在 \(n \leq 500\) 的范围下，最多只有一个大于等于 \(22\) 的质因子。
因此我们可以枚举这个质因子，而将剩下的质因子（也就 \(8\) 个了）按照上面的常规方式转移。
具体来说，我们把所有数按大质因子从小到大的顺序排列（两个大质因子相同的数不能选，当然两个没有大质因子的数显然是可能同时选的）。
我们设 \(g_1(p,q)\) 为第一个集合包含大质因子的方案数，同理 \(g_2(p,q)\) 为第二个集合包含大质因子的方案数。
对一段大质因子相同的数，我们将 \(f\) 复制给 \(g_1\) 和 \(g_2\)，在 \(g_1\) 和 \(g_2\) 内部采用原始的暴力 DP 方法进行转移。
将这段大质因子处理完后，将 \(g_1\) 和 \(g_2\) 合并到 \(f\) 中，具体的合并方式为：
$$f(p,q)=g_1(p,q)+g_2(p,q)-f(p,q)$$
（最后减去的是两个集合都不选该大质因子的情况，因为它已经在 \(g_1,g_2\) 中被重复统计了）
最后答案显然是：
$$\sum_{0 \leq p,q \leq 255}f_{p,q}$$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
int sta,p;
}a[505];
const int pri[]={0,2,3,5,7,11,13,17,19};
long long f[305][305],g1[305][305],g2[305][305];
bool cmp(const node&a,const node&b)
{
return a.p<b.p;
}
int main()
{
int n,p;
long long ans=0;
cin>>n>>p;
for(int i=2;i<=n;i++)
{
int p=i;
for(int j=1;j<=8;j++)
{
while(p%pri[j]==0)
p/=pri[j],a[i].sta|=(1<<(j-1));
}
a[i].p=p;
}
sort(a+2,a+n+1,cmp);
f[0][0]=1;
for(int i=2;i<=n;i++)
{
if(i==2||a[i].p!=a[i-1].p||a[i].p==1)
{
memcpy(g1,f,sizeof(f));
memcpy(g2,f,sizeof(f));
}
for(int j=255;j>=0;j--)
for(int k=255;k>=0;k--)
{
if(j&k)continue;
if((a[i].sta&k)==0)g1[j|a[i].sta][k]=(g1[j|a[i].sta][k]+g1[j][k])%p;
if((a[i].sta&j)==0)g2[j][k|a[i].sta]=(g2[j][k|a[i].sta]+g2[j][k])%p;
}
if(i==n||a[i].p!=a[i+1].p||a[i].p==1)
for(int j=0;j<=255;j++)
for(int k=0;k<=255;k++)
f[j][k]=((g1[j][k]+g2[j][k]-f[j][k])%p+p)%p;
}
for(int j=0;j<=255;j++)
for(int k=0;k<=255;k++)
if((j&k)==0)ans=(ans+f[j][k])%p;
cout<<ans<<endl;
return 0;
}