正题

---

题目大意

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

求所有方案的权值和，对$998244353$取模。

$1\le T\le 10,1\le n\le 70,1\le m\le 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<cstdio> #include<cstring> #include<algorithm> 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)<<m)|((p>0)<<j);} void work(int g,int sq,int sp,int w){int S=(sq<<m+1)|sp;(f[g][S]+=w)%=P;if(!v[g][S])v[g][S]=1,s[g][l[g]++]=S;return; } int main() {freopen("grid.in","r",stdin);freopen("grid.out","w",stdout); scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);int g=0,MS=(1<<m+1)-1;memset(f,0,sizeof(f));memset(v,0,sizeof(v));l[1]=0;s[0][0]=0;l[0]=1;f[0][0]=1;for(int i=0;i<n;i++){for(int j=0,lim;j<m;j++){scanf("%d",&lim);g^=1;for(int p=0;p<l[g];p++)v[g][s[g][p]]=f[g][s[g][p]]=0;l[g]=0;for(int x=0;x<=4;x++){if(lim!=-1&&lim!=x)continue;for(int p=0;p<l[!g];p++){int S=s[!g][p],zq=x,zp=x;int sq=S>>m+1,sp=S-(sq<<m+1);int kq=(j?((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<<m)^(1<<j);sp&=MS^(1<<m)^(1<<j);for(int rq=0;rq<=kq;rq++)for(int rp=0;rp<=kp;rp++){if(zq<rq||zp<rp||zq-rq>2||zp-rp>2)continue;work(g,ges(sq^(rq<<j-1),j,zq-rq),ges(sp^(rp<<j-1),j,zp-rp),f[!g][S]);}}}}g^=1;for(int p=0;p<l[g];p++)v[g][s[g][p]]=f[g][s[g][p]]=0;l[g]=0;for(int p=0;p<l[!g];p++){int S=s[!g][p];int sq=S>>m+1,sp=S-(sq<<m+1);if(((sq>>m)&1)|((sp>>m)&1))continue;work(g,sq,sp,f[!g][S]);}}printf("%d\n",f[g][0]);}return 0; }

总结

以上是生活随笔为你收集整理的YbtOJ-方格填写【插头dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。