[洛谷 3734][HAOI2017]方案数

题目链接

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

题解

先考虑没有限制格的情况。

注意到这时候我们能走的方案数只和 \(x,y,z\) 的二进制表示中的 \(1\) 的数量有关。因此我们设 \(f(i,j,k)\) 表示 \(x\) 中有 \(i\) 个位,\(y\) 中有 \(j\) 个位,\(z\) 中有 \(k\) 个位值为 \(1\) 时的方案数。

根据排列组合的规律,可以得到如下转移方程:

$$f(i,j,k)=\sum_{x=1}^{i} f(i-x,j,k)\times C_i^x + \sum_{y=1}^{j} f(i,j-y,k)\times C_j^y + \sum_{z=1}^{k} f(i,j,k-z)\times C_k^z$$

现在我们需要解决有限制点的情况。我们可以利用补集转化的思想,从总方案数中扣去不合法的方案数。

先将限制点坐标按 \(x\) 坐标第一关键字,\(y\) 坐标第二关键字,\(z\) 坐标第三关键字排序,并将终点也插入到限制点当中去。

我们设 \(g_i\) 表示到第 \(j\) 个点的合法方案数(这个可以直接根据 \(f\) 数组的值求出来)。我们枚举能到达 \(i\) 的前驱节点 \(j\) 点,从 \(g_i\) 中扣去从 \(j\) 到 \(i\) 的方案数(这些方案肯定是不合法的)。

这样我们就可以算出到终点的方案数了,时间复杂度是 \(O(o^2)\) 的。

到这里还有一个细节:我们需要一个高效地求出一个二进制数中 \(1\) 的个数(也就是 popcount)的算法。直接模拟是 \(O(\log n)\) 的,而在本题需要大量查询的情况下,分块打表(将 64 位二进制数分为 4 个 16 位二进制数再查表计算)的效率则要高得多。

#include <iostream>
#include <algorithm>
#define MOD 998244353
#define BMAX 65535
using namespace std;
struct point
{
 long long x,y,z;
}p[10005];
long long c[65][65],f[65][65][65],g[10005];
int bit[65536];
bool cmp(const point&a,const point&b)
{
 return a.x<b.x||(a.x==b.x&&(a.y<b.y||(a.y==b.y&&a.z<b.z)));
}
int normal_popcount(int x)
{
 int ans=0;
 while(x)
 {
  ans+=x&1;
  x>>=1;
 }
 return ans;
}
int popcount(long long x)
{
 return bit[x&BMAX]+bit[(x>>16)&BMAX]+bit[(x>>32)&BMAX]+bit[(x>>48)&BMAX];
}
int main()
{
 long long n,m,r,o;
 cin>>n>>m>>r>>o;
 for(int i=1;i<=o;i++)
  cin>>p[i].x>>p[i].y>>p[i].z;
 o++;
 p[o].x=n,p[o].y=m,p[o].z=r;
 sort(p+1,p+o+1,cmp);
 for(int i=0;i<=BMAX;i++)
  bit[i]=normal_popcount(i);
 c[0][0]=1;
 for(int i=1;i<=64;i++)
 {
  c[i][0]=1;
  for(int j=1;j<=i;j++)
   c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
 }
 f[0][0][0]=1;
 for(int i=0;i<=64;i++)
  for(int j=0;j<=64;j++)
   for(int k=0;k<=64;k++)
   {
    if(i)
     for(int l=1;l<=i;l++)
      f[i][j][k]=(f[i][j][k]+f[i-l][j][k]*c[i][l])%MOD;
    if(j)
     for(int l=1;l<=j;l++)
      f[i][j][k]=(f[i][j][k]+f[i][j-l][k]*c[j][l])%MOD;
    if(k)
     for(int l=1;l<=k;l++)
      f[i][j][k]=(f[i][j][k]+f[i][j][k-l]*c[k][l])%MOD;
   }
 for(int i=1;i<=o;i++)
 {
  long long x=p[i].x,y=p[i].y,z=p[i].z;
  g[i]=f[popcount(x)][popcount(y)][popcount(z)];
  for(int j=1;j<i;j++)
  {
   long long x1=p[j].x,y1=p[j].y,z1=p[j].z;
   if((x1&x)!=x1||(y1&y)!=y1||(z1&z)!=z1)continue;
   int bx=popcount(x^x1),by=popcount(y^y1),bz=popcount(z^z1);
   g[i]=((g[i]-g[j]*f[bx][by][bz])%MOD+MOD)%MOD;
  }
 }
 cout<<g[o]<<endl;
 return 0;
}

发表评论

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