题解
这个出题人完美诠释了什么叫
用心出题，用脚造数据
算完复杂度怎么也得\(O(o^2 * 200)\)略微跑不满，但是有8个测试点虽然有障碍但是一个障碍都不在路径上，2个测试点只有10来个点在路径上
这么轻松愉快的嘛？？？？
如果没有障碍的话只和\(1\)的数量有关
那么我们设\(dp[i][j][k]\)表示第一维有\(i\)个\(1\)第二维有\(j\)个\(1\)第三维有\(k\)个\(1\)的方案数
转移的时候枚举哪一位增加了多少1
方案数是
\(\binom{i}{h}\cdot dp[i - h][j][k] \rightarrow dp[i][j][k]\)
\(\binom{j}{h}\cdot dp[i][j - h][k] \rightarrow dp[i][j][k]\)
\(\binom{k}{h}\cdot dp[i][j][k - h] \rightarrow dp[i][j][k]\)
然后就成功得到80分做完预处理了
然后我没啥好想法了我觉得就设一个\(f[i][j]\)表示走到第\(i\)个点至少经过\(j\)个点
估算一下第二维最多是60 +60 + 60
然后我按照每个点的第一维排序，第一维相等按第二维，第二维相等按第三维，这就是拓扑序了，就暴力更新一下就好了吧（因为感觉跑满复杂度的点不太好造）
结果这不满的也太厉害了吧= =，实际上o<=20了解一下？？？？
update:翻了stdcall的代码发现根本用不上第二维，因为每次转移的时候多了一个点相当于取反一次，所以就是\(O(o^2)\)的
我好菜啊QAQ
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define MAXN 100005
#define mo 974711
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 998244353;
int64 N,M,R,x[10005],y[10005],z[10005];
int dp[64][64][64],C[64][64],ans;
bool vis[10005];
int f[10005],O,cntx[10005],cnty[10005],cntz[10005],id[10005],idx,cn,cm,cr;
int64 lowbit(int64 x) {return x & (-x);}
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int calc(int64 x) {
int cnt = 0;
while(x) {
++cnt;
x -= lowbit(x);
}
return cnt;
}
bool cmp(int a,int b) {
if(x[a] != x[b]) return x[a] < x[b];
if(y[a] != y[b]) return y[a] < y[b];
return z[a] < z[b];
}
void Solve() {
read(N);read(M);read(R);
C[0][0] = 1;
for(int i = 1 ; i <= 62 ; ++i) {
C[i][0] = 1;
for(int j = 1 ; j <= i ; ++j) {
C[i][j] = inc(C[i - 1][j - 1],C[i - 1][j]);
}
}
dp[0][0][0] = 1;
for(int i = 0 ; i <= 62 ; ++i) {
for(int j = 0 ; j <= 62 ; ++j) {
for(int k = 0 ; k <= 62 ; ++k) {
if(!(i + j + k)) continue;
for(int h = 1 ; h <= i ; ++h) dp[i][j][k] = inc(dp[i][j][k],mul(dp[i - h][j][k],C[i][h]));
for(int h = 1 ; h <= j ; ++h) dp[i][j][k] = inc(dp[i][j][k],mul(dp[i][j - h][k],C[j][h]));
for(int h = 1 ; h <= k ; ++h) dp[i][j][k] = inc(dp[i][j][k],mul(dp[i][j][k - h],C[k][h]));
}
}
}
ans = dp[cn = calc(N)][cm = calc(M)][cr = calc(R)];
read(O);
for(int i = 1 ; i <= O ; ++i) {
read(x[i]);read(y[i]);read(z[i]);
cntx[i] = calc(x[i]);cnty[i] = calc(y[i]);cntz[i] = calc(z[i]);
if((x[i] & N) == x[i] && (y[i] & M) == y[i] && (z[i] & R) == z[i]) id[++idx] = i;
}
sort(id + 1,id + idx + 1,cmp);
for(int i = 1 ; i <= idx ; ++i) {
int u = id[i];
f[u] = inc(f[u],MOD - dp[cntx[u]][cnty[u]][cntz[u]]);
ans = inc(ans,mul(f[u],dp[cn - cntx[u]][cm - cnty[u]][cr - cntz[u]]));
for(int k = i + 1 ; k <= idx ; ++k) {
if((x[u] & x[id[k]]) == x[u] && (y[u] & y[id[k]]) == y[u] && (z[u] & z[id[k]]) == z[u]) {
f[id[k]] = inc(f[id[k]],mul(f[u],MOD - dp[cntx[id[k]] - cntx[u]][cnty[id[k]] - cnty[u]][cntz[id[k]] - cntz[u]]));
}
}
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}