哎，为什么我怎么搞都是30分呢？

代码：

#include<bits/stdc++.h>
using namespace std;
int n,mod,ans,dp1[300][300],dp2[300][300],dp[300][300];
int prime[8]={2,3,5,7,11,13,17,19};
struct node{
	int num,big,s;
} a[510];
int main(){
	scanf("%d%d",&n,&mod);
	for(int i=2;i<=n;i++){
		a[i-1].num=i;
		a[i-1].big=-1;
		a[i-1].s=0;
		int t=i;
		for(int j=0;j<8;j++){
			if(t%prime[j]==0){
				a[i-1].s+=(1<<j);
				while(t%prime[j]) t/=prime[j];
			}
		}
		if(t>1) a[i-1].big=t;
	}
	dp[0][0]=1;
	for(int k=1;k<n;k++){
		bool flag=(k==1||a[k].big==-1||a[k].big!=a[k-1].big);
		if(flag){
			memcpy(dp1,dp,sizeof(dp1));
			memcpy(dp2,dp,sizeof(dp2));
		}
		for(int i=255;i>=0;i--){
			for(int j=255;j>=0;j--){
				if(i&j) continue;
				if(!(a[k].s&j)) dp1[i|a[k].s][j]=(dp1[i|a[k].s][j]+dp1[i][j])%mod;
				if(!(a[k].s&i)) dp2[i][j|a[k].s]=(dp2[i][j|a[k].s]+dp2[i][j])%mod;
			}
		}
		if(flag){
			for(int i=0;i<=255;i++){
				for(int j=0;j<=255;j++){
					if(i&j) continue;
					dp[i][j]=(dp1[i][j]+dp2[i][j]-dp[i][j])%mod;
				}
			}
		}
	}
	for(int i=0;i<=255;i++){
		for(int j=0;j<=255;j++){
			if(i&j) continue;
			ans=(ans+dp[i][j])%mod;
		}
	}
	printf("%d",ans);
	return 0;
}

评测：

https://www.luogu.com.cn/record/90217428