正題

---

題目大意

給出$n\times m$的網格填著$?1～4$的數字，對于將所有的$?1$填上$0～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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。