题意简述
在无限大的三维空间中走，有3种位移操作：
- ((x,y,z) o (x',y,z)) 当且仅当 ((x&x')=x)
- ((x,y,z) o (x,y',z)) 当且仅当 ((y&y')=y)
- ((x,y,z) o (x,y,z')) 当且仅当 ((z&z')=z)
给定 (o) 个点不能走。求从 ((0,0,0)) 到 ((n,m,r)) 的方案数，对998244353取模。
(oleq 10^4)
(m,n,r leq 10^{18})
想法
首先，这种若干个点不让走、求路径数的问题是经典的容斥问题。
设 (g[i]) 表示路径中第一个经过的障碍点为 (i) 的路径数。
为方便表示，不妨设 (trans(x,y)) 表示从点 (x) 到 (y) 的总路径数（经不经过障碍都算）。
(g[i]=trans(起点，i)-sumlimits_{j=1}^{i-1} g[j] imes trans(j,i))
如果 (trans(x,y)) 可以 (O(1)) 得到的话，总转移复杂度就是 (O(o^2)) 没有问题。
观察此题中的位移操作，发现 (x) 中为1的二进制位上 (x') 也为1，且 (x') 中的1的个数比 (x) 中的多。（(y与y',z与z') 也是这样）
所以转移只与每维的坐标的二进制中1的个数之差有关。
于是可以 (dp) 进行预处理。
(dp[a][b][c]) 表示从起点到终点，每维的1个数之差分别为 (a,b,c) ，(a,b,c leq 60)
有 (dp[a][b][c]=sumlimits_{i=0}^{a-1} inom{a}{i} dp[i][b][c] + sumlimits_{i=0}^{b-1} inom{b}{i} dp[a][i][c] + sumlimits_{i=0}^{c-1} inom{c}{i} dp[a][b][i])
然后就可以了。
总结
模型
经典容斥！！！
(g[i]=trans(起点，i)-sumlimits_{j=1}^{i-1} g[j] imes trans(j,i))
技巧
求一个较大数二进制中1的个数：打表+分块。
int dabiao(){
for(int i=0;i<65536;i++) {
bt[i]=0;
x=i;
while(x) bt[i]+=(x&1),x>>=1;
}
}
int cal(ll x) {
int t=0;
while(x>=65536){
t+=bt[x&65535];
x>>=16;
}
return t+bt[x];
}
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define P 998244353
using namespace std;
const int N = 10005;
typedef long long ll;
ll read(){
ll x=0;
char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
ll n,m,r;
int o;
struct data{
ll x,y,z;
int cx,cy,cz;
bool operator < (const data &b) const{
return x<b.x || (x==b.x && y<b.y) || (x==b.x && y==b.y && z<b.z);
}
}d[N];
int f[62][62][62],g[N],c[62][62],bt[65536];
int Plus(int x,int y) { return x+y>=P ? x+y-P : x+y; }
int Minus(int x,int y) { return x>=y ? x-y : x-y+P; }
void init(){
c[0][0]=1;
for(int i=1;i<=60;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++) c[i][j]=Plus(c[i-1][j-1],c[i-1][j]);
}
for(int i=0;i<=60;i++)
for(int j=0;j<=60;j++)
for(int k=0;k<=60;k++){
if(!i && !j && !k) { f[i][j][k]=1; continue; }
f[i][j][k]=0;
for(int t=0;t<i;t++)
f[i][j][k]=Plus(f[i][j][k],1ll*f[t][j][k]*c[i][t]%P);
for(int t=0;t<j;t++)
f[i][j][k]=Plus(f[i][j][k],1ll*f[i][t][k]*c[j][t]%P);
for(int t=0;t<k;t++)
f[i][j][k]=Plus(f[i][j][k],1ll*f[i][j][t]*c[k][t]%P);
}
int x;
for(int i=0;i<65536;i++) {
bt[i]=0;
x=i;
while(x) bt[i]+=(x&1),x>>=1;
}
}
int cal(ll x) {
int t=0;
while(x>=65536){
t+=bt[x&65535];
x>>=16;
}
return t+bt[x];
}
int main()
{
n=read(); m=read(); r=read();
o=read();
for(int i=1;i<=o;i++) { d[i].x=read(); d[i].y=read(); d[i].z=read(); }
++o;
d[o].x=n; d[o].y=m; d[o].z=r;
sort(d+1,d+1+o);
init();
for(int i=1;i<=o;i++){
d[i].cx=cal(d[i].x); d[i].cy=cal(d[i].y); d[i].cz=cal(d[i].z);
g[i]=f[d[i].cx][d[i].cy][d[i].cz];
for(int j=1;j<i;j++)
if((d[j].x&d[i].x)==d[j].x && (d[j].y&d[i].y)==d[j].y && (d[j].z&d[i].z)==d[j].z)
g[i]=Minus(g[i],1ll*g[j]*f[d[i].cx-d[j].cx][d[i].cy-d[j].cy][d[i].cz-d[j].cz]%P);
}
printf("%d
",g[o]);
return 0;
}