题目
题解
先考虑没有障碍的情况
设$f_{i,j,k}$为第一维二进制下有$i$个$1$，第二维二进制下有$j$个$1$，第三维二进制下有$k$个$1$的方案数，每次就从$f_{i-l,j,k},f_{i,j-l,k},f_{i,j,k-l}$转移过来即可
设$F_i$表示经过第$i$个障碍，但是不经过前$i-1$个障碍的方案数，容斥即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int _=101,MAX=1e4+5,mod=998244353;
struct p{
LL x,y,z;
int nx,ny,nz;
bool operator< (const p &a)
const{
if(x!=a.x) return x<a.x;
if(y!=a.y) return y<a.y;
return z<a.z;
}
}t[MAX];
int o,cnt,n,m,r,ans;
LL N,M,R;
int F[MAX];
int C[_][_];
int f[_][_][_];
int GET_NUM(LL x)
{
int num=0;
while(x) x&=x-1,++num;
return num;
}
int main()
{
scanf("%lld%lld%lld%d",&N,&M,&R,&o),n=GET_NUM(N),m=GET_NUM(M),r=GET_NUM(R);
for(int i=1;i<=o;++i)
{
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
if((N&x)==x&&(M&y)==y&&(R&z)==z) t[++cnt]=(p){x,y,z,GET_NUM(x),GET_NUM(y),GET_NUM(z)};
}
sort(t+1,t+1+cnt);
for(int i=0;i<_;++i)
{
C[i][0]=C[i][i]=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<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k<=r;++k)
if(i||j||k) for(int l=1;l<=max(i,max(j,k));++l)
(f[i][j][k]+=((l<=i?1ll*C[i][l]*f[i-l][j][k]%mod:0)+(l<=j?1ll*C[j][l]*f[i][j-l][k]%mod:0)+(l<=k?1ll*C[k][l]*f[i][j][k-l]%mod:0))%mod)%=mod;
ans=f[n][m][r];
for(int i=1;i<=cnt;++i)
{
F[i]=(F[i]-f[t[i].nx][t[i].ny][t[i].nz]+mod)%mod,(ans+=1ll*F[i]*f[n-t[i].nx][m-t[i].ny][r-t[i].nz]%mod)%=mod;
for(int j=i+1;j<=cnt;++j)
if((t[j].x&t[i].x)==t[i].x&&(t[j].y&t[i].y)==t[i].y&&(t[j].z&t[i].z)==t[i].z) F[j]=(F[j]-1ll*F[i]*f[t[j].nx-t[i].nx][t[j].ny-t[i].ny][t[j].nz-t[i].nz]%mod+mod)%mod;
}
return printf("%d",ans),0;
}
