挺神的一道题 ~
由于两个人选的数字不能有互质的情况, 所以说对于一个质因子来说, 如果 1 选了, 则 2 不能选任何整除该质因子的数.
然后, 我们发现对于 1 ~ 500 的数字来说, 只可能有一个大于 $\sqrt 500$ 的质因子 (两个的话乘积就超过 500 了)
而不大于 $\sqrt 500$ 的质因子总数只有 8 个, 所以可以对这 8 个质因子状压.
我们先假设所有数字都 $\eqslant 30$, 即所有质因子都 $leqslant \sqrt 500$.
定义状态 dp[i][j] 表示第一个人选的质因子集合为 $i$, 第二个人选的质因子集合为 $j$.
那么直接更新 $dp[i|sta][j]+=dp[i][j]$ (sta 与 k 无交集)
对于第二个维度同理.
由于我们用滚动数组, 所以还要定义 f1[i][j], f2[i][j] 表示第一个人 / 第二个人 和 第二个人 / 第一个人 状态下的方案数.
这个转移弄完之后, 我们再考虑加入大于 $\sqrt 500$ 的质因子的情况:
令这个质因子为 $x$, 那么会有一段数字都包含这个 $x$, 显然这些数中只能让 1 个人去选择这个质因子.
我们沿用上面那个 f1[i][j], f2[i][j] 来更新, 然后对于这一段的开始位置直接令 f1=f2=dp, 其余的正常 dp.
处理完这段的时候还要减去两个数都不选的情况.
最后 dp'[i][j]=f1[i][j]+f2[i][j]-dp[i][j].
- code:
- #include <bits/stdc++.h>
- #define N 703
- #define LL long long
- #define setIO(s) freopen(s".in","r",stdin)
- using namespace std;
- int n;
- int poww[N];
- LL ans,mod;
- LL dp[N][N],f1[N][N],f2[N][N];
- int p[13]={0,2,3,5,7,11,13,17,19,23};
- struct data
- {
- int num,bi,sta;
- }a[N];
- bool cmp(data a,data b)
- {
- return a.bi<b.bi;
- }
- void init(int num)
- {
- int i,j,v=num,bi=0;
- for(i=1;i<=8;++i)
- {
- if(v%p[i]==0)
- {
- a[num].sta|=poww[i];
- while(v%p[i]==0) v/=p[i];
- }
- }
- if(v>1) bi=v;
- a[num].bi=bi;
- a[num].num=num;
- }
- int main()
- {
- // setIO("input");
- int i,j;
- scanf("%d%lld",&n,&mod);
- for(i=1;i<=12;++i) poww[i]=(1<<(i-1));
- for(i=2;i<=n;++i) init(i);
- sort(a+2,a+1+n,cmp);
- dp[0][0]=1ll;
- for(i=2;i<=n;++i)
- {
- if(i==2||!a[i].bi||a[i].bi!=a[i-1].bi)
- {
- memcpy(f1,dp,sizeof(dp));
- memcpy(f2,dp,sizeof(dp));
- }
- for(j=255;j>=0;--j)
- {
- for(int k=255;k>=0;--k)
- {
- if((j&a[i].sta)==0) f1[j][k|a[i].sta]=(f1[j][k|a[i].sta]+f1[j][k])%mod;
- if((k&a[i].sta)==0) f2[j|a[i].sta][k]=(f2[j|a[i].sta][k]+f2[j][k])%mod;
- }
- }
- if(i==n||!a[i].bi||a[i].bi!=a[i+1].bi)
- {
- for(j=0;j<=255;++j)
- {
- for(int k=0;k<=255;++k)
- {
- dp[j][k]=(f1[j][k]+f2[j][k]-dp[j][k]+mod)%mod;
- }
- }
- }
- }
- LL ans=0ll;
- for(i=0;i<=255;++i) for(j=0;j<=255;++j) if((i&j)==0) (ans+=dp[i][j])%=mod;
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3313677.html