正题

题目大意

给出\(n\times m\)的网格填着\(-1\sim 4\)的数字，对于将所有的\(-1\)填上\(0\sim 4\)的方案中，定义方案\(X\)的权值，设在相邻网格之间连线（每对只能连一条）使得每个网格连出去的边数恰好位数字的方案数为\(f(X)\)，那么权值为\(f^2(X)\)。

求所有方案的权值和，对\(998244353\)取模。

\(1\leq T\leq 10,1\leq n\leq 70,1\leq m\leq 6\)

解题思路

主要的难点在这个平方处，我们有道经典处理方案数平方的例题[NOI2009]管道取珠，做法就是同时维护两个共线推进的方案，这样每对方案之间都有贡献，方案数就平方了。

但是这样的状态也是平方的，我们需要考虑压缩一下状态，正常来说的插头\(dp\)可能是\(O(5^m)\)的状态，但是注意到每队网格只能连一条边，所以对于每个块最多只能剩下插头数的状态，也就是除了当且枚举快左边那个以外都是\(2\)个状态，这样状态就很少了，只有\(96\)种，直接平方做然后插头\(dp\)转移即可。

code

#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include
#include
#include
using namespace std;
const int P=998244353;
int T,n,m,f[2][16384],v[2][16384],s[2][16384],l[2];
int ges(int s,int j,int p)
{return s|((p>1)<0)<>m+1,sp=S-(sq<>j-1)&1):0),kp=(j?((sp>>j-1)&1):0);
						zq-=((sq>>m)&1)+((sq>>j)&1);kq-=((sq>>m)&1);
						zp-=((sp>>m)&1)+((sp>>j)&1);kp-=((sp>>m)&1);
						if(zq<0||zp<0)continue;
						sq&=MS^(1<2||zp-rp>2)continue;
								work(g,ges(sq^(rq<>m+1,sp=S-(sq<>m)&1)|((sp>>m)&1))continue;
				work(g,sq,sp,f[!g][S]);
			}
		}
		printf("%d\n",f[g][0]);
	}
	return 0;
}