题目链接
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; }