[洛谷 2150][NOI2015]寿司晚宴

题目链接

https://www.luogu.com.cn/problem/P2150

题解

注意到我们的可用集合只与用到的质因子有关,因此我们可以以用到的质因子为状态进行转移。

设 \(f(p,q)\) 为第一个集合的质因子状态为 \(p\),第二个质因子的状态为 \(q\) 时的方案数,转移时要求 \(p\) 和 \(q\) 无交集即可。

然而 \(n \leq 500\) 的时候质因子数量很多,压缩起来空间不够。

注意到一个数 \(x\) 的质因数满足这样的性质:大于等于 \(\sqrt x\) 的质因子最多只有一个。这意味着在 \(n \leq 500\) 的范围下,最多只有一个大于等于 \(22\) 的质因子。

因此我们可以枚举这个质因子,而将剩下的质因子(也就 \(8\) 个了)按照上面的常规方式转移。

具体来说,我们把所有数按大质因子从小到大的顺序排列(两个大质因子相同的数不能选,当然两个没有大质因子的数显然是可能同时选的)。

我们设 \(g_1(p,q)\) 为第一个集合包含大质因子的方案数,同理 \(g_2(p,q)\) 为第二个集合包含大质因子的方案数。

对一段大质因子相同的数,我们将 \(f\) 复制给 \(g_1\) 和 \(g_2\),在 \(g_1\) 和 \(g_2\) 内部采用原始的暴力 DP 方法进行转移。

将这段大质因子处理完后,将 \(g_1\) 和 \(g_2\) 合并到 \(f\) 中,具体的合并方式为:

$$f(p,q)=g_1(p,q)+g_2(p,q)-f(p,q)$$

(最后减去的是两个集合都不选该大质因子的情况,因为它已经在 \(g_1,g_2\) 中被重复统计了)

最后答案显然是:

$$\sum_{0 \leq p,q \leq 255}f_{p,q}$$

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
 int sta,p;
}a[505];
const int pri[]={0,2,3,5,7,11,13,17,19};
long long f[305][305],g1[305][305],g2[305][305];
bool cmp(const node&a,const node&b)
{
 return a.p<b.p;
}
int main()
{
 int n,p;
 long long ans=0;
 cin>>n>>p;
 for(int i=2;i<=n;i++)
 {
  int p=i;
  for(int j=1;j<=8;j++)
  {
   while(p%pri[j]==0)
    p/=pri[j],a[i].sta|=(1<<(j-1));
  }
  a[i].p=p;
 }
 sort(a+2,a+n+1,cmp);
 f[0][0]=1;
 for(int i=2;i<=n;i++)
 {
  if(i==2||a[i].p!=a[i-1].p||a[i].p==1)
  {
   memcpy(g1,f,sizeof(f));
   memcpy(g2,f,sizeof(f));
  }
  for(int j=255;j>=0;j--)
   for(int k=255;k>=0;k--)
   {
    if(j&k)continue;
    if((a[i].sta&k)==0)g1[j|a[i].sta][k]=(g1[j|a[i].sta][k]+g1[j][k])%p;
    if((a[i].sta&j)==0)g2[j][k|a[i].sta]=(g2[j][k|a[i].sta]+g2[j][k])%p;
   }
  if(i==n||a[i].p!=a[i+1].p||a[i].p==1)
   for(int j=0;j<=255;j++)
    for(int k=0;k<=255;k++)
     f[j][k]=((g1[j][k]+g2[j][k]-f[j][k])%p+p)%p;
 }
 for(int j=0;j<=255;j++)
  for(int k=0;k<=255;k++)
   if((j&k)==0)ans=(ans+f[j][k])%p;
 cout<<ans<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注