求从 ((0,0,0)) 走到 ((n,m,r)) 的方案数。(n,m,r leq 10^{18})。每次 (s) 可以移动到一个点 (t), (t) 的该坐标的二进制表示中为 (1) 的位必须包含所有 (s) 的该坐标的二进制表示中为 (1) 为位。同时,有 (o leq 10^4) 个限制点不能经过。(原题题面描述有毒)
Solution
考虑先求出没有障碍时的方案数,显然只和每个坐标上 (1) 个数有关,设 (f[i][j][k]) 表示三个坐标上 (1) 的个数依次为 (i,j,k) 的方案数,预处理组合数后暴力转移 (C_i^l cdot f[i-l][j][k] o f[i][j][k]),其它两维类似
将所有点按每个维度升序排序((x) 为第一关键字,(y) 为第二……),设 (g[i]) 表示走到障碍点 (i) 的方案数,考虑哪些 (j) 能作为转移点,显然必须有 (x_j subseteq x_i, y_j subseteq y_i, z_j subseteq z_i),那么 (g[i]=f[x_i][y_i][z_i]-sum g[j]cdot f[i xor j])
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20005;
const int M = 64;
const int mod = 998244353;
namespace popcnter {
int bt[65536];
int popcnt (int x) {
int t=0;
while(x>=65536){
t+=bt[x&65535];
x>>=16;
}
return t+bt[x];
}
void init() {
for(int i=0;i<65536;i++) {
bt[i]=0;
int x=i;
while(x) bt[i]+=(x&1),x>>=1;
}
}
}
using namespace popcnter;
struct point {
int x,y,z;
bool operator < (const point &b) {
if(x-b.x) return x<b.x;
if(y-b.y) return y<b.y;
return z<b.z;
}
} a[N];
int p,q,r,n,f[M][M][M],g[N],c[M][M];
int cor(int x) {
return (x%mod+mod)%mod;
}
signed main() {
ios::sync_with_stdio(false);
init();
cin>>p>>q>>r;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i].x>>a[i].y>>a[i].z;
}
++n;
a[n].x=p; a[n].y=q; a[n].z=r;
sort(a+1,a+n+1);
f[0][0][0]=1;
for(int i=0;i<M;i++) {
c[i][0]=1;
for(int j=1;j<=i;j++) {
c[i][j]=cor(c[i-1][j-1]+c[i-1][j]);
}
}
for(int i=0;i<M;i++) {
for(int j=0;j<M;j++) {
for(int k=0;k<M;k++) {
if(i+j+k) {
for(int l=1;l<=i;l++) f[i][j][k]=cor(f[i][j][k]+f[i-l][j][k]*c[i][l]);
for(int l=1;l<=j;l++) f[i][j][k]=cor(f[i][j][k]+f[i][j-l][k]*c[j][l]);
for(int l=1;l<=k;l++) f[i][j][k]=cor(f[i][j][k]+f[i][j][k-l]*c[k][l]);
}
}
}
}
for(int i=1;i<=n;i++) {
g[i]=f[popcnt(a[i].x)][popcnt(a[i].y)][popcnt(a[i].z)];
for(int j=1;j<i;j++) {
if((a[i].x&a[j].x)==a[j].x && (a[i].y&a[j].y)==a[j].y && (a[i].z&a[j].z)==a[j].z) {
g[i]=cor(g[i]-g[j]*f[popcnt(a[i].x^a[j].x)]
[popcnt(a[i].y^a[j].y)][popcnt(a[i].z^a[j].z)]);
}
}
}
cout<<g[n];
}