改了一个小细节，结果尴尬的发现，样例3过不了……
```cpp
#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++){
if(k==1||a[k].big==-1||a[k].big!=a[k-1].big){
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(k==n-1||a[k].big==-1||a[k].big!=a[k+1].big){
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;
}
```
by YuRuochen @ 2022-10-16 18:36:06
忘排序了，排了序，可是样例3仍然过不了……
```cpp
#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];
bool cmp(node a,node b){
return a.big<b.big;
}
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;
}
sort(a+1,a+n,cmp);
dp[0][0]=1;
for(int k=1;k<n;k++){
if(k==1||a[k].big==-1||a[k].big!=a[k-1].big){
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(k==n-1||a[k].big==-1||a[k].big!=a[k+1].big){
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;
}
```
by YuRuochen @ 2022-10-16 18:39:06
问题已解决，此贴告终
by YuRuochen @ 2022-10-16 19:07:36