P3734 [HAOI2017] 方案数
相当于将二进制下为 \(0\) 的位置选至少 \(1\) 个变成 \(1\)。
设 \(f_{i,j,k}\) 表示在三维坐标二进制下分别改变了 \(x,y,z\) 个 \(0\) 的方案数。
注意这里不是三维的答案相乘，因为是有改变相当于移动是有顺序的，如 \((0,0,0)\to(0,1,0)\to(1,1,0)\) 与 \((0,0,0)\to(1,0,0)\to(1,1,0)\) 是两种方案。
有转移：
\[f_{i,j,k}=
\sum_{x=1}^{i-1} \binom{i}{x}f_{x,j,k}
+\sum_{x=1}^{j-1} \binom{j}{x}f_{i,x,k}
+\sum_{x=1}^{k-1} \binom{k}{x}f_{i,j,x}
\]
解释（第一项，其它的是类似的）:
对于 \(i\)，可以考虑少改变 \(i-x\) 位得到 \(x\)。这些位置可以在 \(i\) 个位置任选，方案数为 \(\dbinom{i}{i-x}=\dbinom{i}{x}\)。
由于每次移动坐标只能增大，先将所有障碍按字典序排序消除 DP 的后效性。
设 \(g_i\) 为到达第 \(i\) 个点且不经过前 \(i-1\) 个点的方案数。
转移时考虑容斥，用全部方案数减去不合法的方案数。
对于每个 \(j<i\)，若满足 \(x_j\subseteq x_i\wedge y_j\subseteq y_i\wedge z_j\subseteq z_i\)，则可能到达 \(i\)。
记 \(P(x)\) 表示 \(x\) 二进制下 \(1\) 的数量。
从 \(j\) 到达 \(i\) 有 \(f_{P(x_i)-P(x_j),P(y_i)-P(y_j),P(z_i)-P(z_j)}\) 种方案，记为 \(k\)。
因此有：
\[g_{i}=f_{P(x_i),P(y_i),P(z_i)}-\sum_{j=1}^{i-1} [x_j\subseteq x_i\wedge y_j\subseteq y_i\wedge z_j\subseteq z_i]k\cdot g_j
\]
为方便统计答案可以将终点也看作障碍点，由题目约束可知其排序后的位置一定在最后一个，答案即为 \(g_{o+1}\)。
#include<bits/stdc++.h>
#define P(x) __builtin_popcountll(x)
using namespace std;
using ll=long long;
const int V=70,N=10005,P=998244353;
int n,f[N],C[V][V],vis[V];
struct Point{ll x,y,z;}a[N];
int T(int x){if(vis[x]) return vis[x];int res=0;for(int i=0;i<x;i++) res=(res+1ll*T(i)*C[x][i])%P;return res;
}
int DP(int x,int y,int z){return 1ll*T(x)*T(y)%P*T(z)%P;}
int main(){vis[0]=1;for(int i=0;i<V;i++) C[i][0]=1;for(int i=1;i<V;i++) for(int j=1;j<=i;j++)(C[i][j]=C[i-1][j-1]+C[i-1][j])>P?(C[i][j]-=P):0;scanf("%lld%lld%lld%d",&a[0].x,&a[0].y,&a[0].z,&n);for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);sort(a,a+n+1,[](Point u,Point v){return u.x^v.x?u.x<v.x:u.y^v.y?u.y<v.y:u.z<v.z;});auto Out=[](int x,int y){return a[x].x&a[y].x^a[y].x|a[x].y&a[y].y^a[y].y|a[x].z&a[y].z^a[y].z;};for(int i=0;i<=n;i++){f[i]=DP(P(a[i].x),P(a[i].y),P(a[i].z));for(int j=0;j<i;j++) if(!Out(i,j))f[i]=(f[i]-1ll*f[j]*DP(P(a[i].x^a[j].x),P(a[i].y^a[j].y),P(a[i].z^a[j].z)))%P;}return printf("%d",(f[n]+P)%P),0;
}