题目链接:戳我
30pts还是很好写的,因为30以内的质因数就没有几个,直接状压就可以了.
但是如果范围扩大到500呢?我们考虑后面的数怎么处理.
首先观察到19之后的数最多只能出现一次,那么我们直接状压这前八个质数就行了.后面的我们可以手动添加一下(为了方便,对于当前遍历的值,下面我们称前八个为小因数,后面的为大因数)
处理出来每个数的小因数的状态,方便下面转移.同时也处理出来它的大因数.而且我们知道大因数应该排序一下(因为相同的肯定要一起处理)--->大概就是一个分块的思想,因为一个质因数只能放到一个集合中.
具体来讲,是开一个数组(dp[i][j])表示A状态为i,B状态为j,方案数.然后两个辅助数组(f1[i][j])表示A状态为i,B状态为j,当前这个数的大因数给了A,(f2[i][j])表示A状态为i,B状态为j,当前这个数的大因数给了B.
(f1[dep][i|now_s][j]+=f1[dep-1][i][j])
(f2[dep][i][j|now_s]+=f2[dep-1][i][j])
这个过程可以用滚动数组,或者从后往前更新来消除后效性.
处理完只有小因数的数(他们的大因数为0,排在前面)之后,我们用(f1[i][j],f2[i][j])去更新(dp[i][j])
(dp[i][j]=f1[i][j]+f2[i][j]-dp[i][j])
(注意这不是一个方程qwq)
为什么后面要减去呢?因为我们现在是想综合当前这个大因数放到两个集合中的情况总和,加起来的话,前面([i][j])的情况就算重了QAQ......然后每次在和后面的那个数的大因数不一样的时候就这样更新一下.就可以了.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 255
using namespace std;
int n,mod;
int prime[8]={2,3,5,7,11,13,17,19};
long long ans;
long long dp[MAXN+10][MAXN+10],f1[MAXN+10][MAXN+10],f2[MAXN+10][MAXN+10];
struct Node{int op,s;}node[510];
inline bool cmp(Node x,Node y){return x.op<y.op;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
// freopen("ce.out","w",stdout);
#endif
scanf("%d%d",&n,&mod);
for(int i=2;i<=n;i++)
{
int cur=i;
for(int j=0;j<8;j++)
{
if(cur%prime[j]==0)
{
node[i].s|=(1<<j);
while(cur&&cur%prime[j]==0) cur/=prime[j];
}
}
node[i].op=cur;
// printf("i=%d op=%d s=%d
",i,node[i].op,node[i].s);
}
sort(&node[2],&node[n+1],cmp);
dp[0][0]=f1[0][0]=f2[0][0]=1;
for(int id=2;id<=n;id++)
{
for(int i=MAXN;i>=0;i--)
for(int j=MAXN;j>=0;j--)
{
if((i&j)!=0) continue;
if((j&node[id].s)==0) f1[i|node[id].s][j]=(f1[i|node[id].s][j]+f1[i][j])%mod;
if((i&node[id].s)==0) f2[i][j|node[id].s]=(f2[i][j|node[id].s]+f2[i][j])%mod;
}
if(node[id].op==1||(node[id].op!=node[id+1].op))
{
// cout<<id<<endl;
for(int i=0;i<=MAXN;i++)
for(int j=0;j<=MAXN;j++)
if((i&j)==0)
dp[i][j]=(f1[i][j]+f2[i][j]+mod-dp[i][j])%mod;
memcpy(f1,dp,sizeof(dp));
memcpy(f2,dp,sizeof(dp));
}
}
for(int i=0;i<=MAXN;i++)
for(int j=0;j<=MAXN;j++)
if((i&j)==0)
ans=(ans+dp[i][j])%mod;
printf("%lld
",ans);
return 0;
}