题目链接
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; }