分析
先考虑一个 $30$ 分做法。
设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。
转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。
注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子，因此我们可以只状压 $<\sqrt{500}$ 的质因子，然后再单独记录一下最大的那个质因子。
我们把 $2\sim n$ 的所有数按照最大质因子从小到大排序，这样子可以把最大质因子相同的数放在一起处理。
同样设 $dp_{i,j}$ 表示小 G 选的数的质因子集合为 $i$ ，小 W 选的数的质因子集合为 $j$ 的方案数。这里滚动掉了一维。
再设 $f_{0/1,i,j}$ 表示当前的最大质因子给了小 G / 小 W，小 G 选的数的质因子集合为 $i$ ，小 W 选的数的质因子集合为 $j$ 的方案数。这里也滚动掉了一维。
每次把 $f_{0/1}$ 的初值设为 $dp$ ，然后把最大质因子相同的数批量转移，最后再将 $f_{0/1}$ 合并到 $dp$ 里去。
具体的合并是 $dp_{i,j}=f_{0,i,j}+f_{1,i,j}-dp_{i,j}$ ，减去 $dp_{i,j}$ 的原因是多算了一次都不选的情况。
最后的答案就是所有的 $dp_{i,j}$ 之和。
具体实现上有一些细节，详见代码。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=500+10;
const int p[8]={2,3,5,7,11,13,17,19};
int n,mod;
int dp[256][256],f[2][256][256];
struct num { int S,r; } a[N];
bool operator <(num a,num b) { return a.r<b.r; }
inline void add(int& x,int y) { x=(x+y)%mod; }
inline void init(int x,int t) {
for (re int i=0;i<8;++i)
while (t%p[i]==0) t/=p[i],a[x].S|=1<<i;
a[x].r=t;
}
int main() {
n=read(),mod=read();
for (re int i=2;i<=n;++i) init(i,i);
sort(a+2,a+n+1); dp[0][0]=f[0][0][0]=f[1][0][0]=1;
for (re int k=2;k<=n;++k) {
for (re int i=255;~i;--i)
for (re int j=255;~j;--j) {
if (i&j) continue;
if (!(j&a[k].S)) add(f[0][i|a[k].S][j],f[0][i][j]);
if (!(i&a[k].S)) add(f[1][i][j|a[k].S],f[1][i][j]);
}
if (a[k].r!=a[k+1].r||a[k].r==1) {
for (re int i=0;i<256;++i)
for (re int j=0;j<256;++j) {
if (i&j) continue;
dp[i][j]=(0ll+f[0][i][j]+f[1][i][j]-dp[i][j]+mod)%mod;
}
memcpy(f[0],dp,sizeof(dp)),memcpy(f[1],dp,sizeof(dp));
}
}
int ans=0;
for (re int i=0;i<256;++i)
for (re int j=0;j<256;++j)
if ((i&j)==0) add(ans,dp[i][j]);
printf("%d\n",ans);
return 0;
}
4 条评论
怎么重写一遍啊
发现自己忘光了
不是n * (3^8)差评
不会，告辞