YbtOJ 504「插头 dp」方格填写

(Updated: )
oi
,

题目链接：YbtOJ #504

小 A 有一个 $n\times m$ 的网格图，其中一些格子中填有 $0\sim 4$ 中的某个数字，其余格子填着 $-1$。

定义一种方格填写方案 $X$ 为 将所有 $-1$ 分别替换为 $0\sim 4$ 中的某个数。两种填写方案不同当且仅当存在至少一个格子填入的数不同。

然后，定义一种填写方案 $X$ 的权值 $f(X)$ 为 在相邻网格（上、下、左、右）之间连边（一对网格之间至多连一条边），使得每个网格连出的边数与其中填写的数字恰好相同 的连边方案数。

小 A 希望你对于所有可能的填写方案 $X$，求出 $f(X)^2$ 的总和。（向 $998244353$ 取模）

$T=10$，$1\le n\le70$，$1\le m\le 6$。

空间限制：$\texttt{32MB}$

Solution

对于 $f(X)^2$ 的计数问题有一个常见转化。

$f(X)^2$ 可以视作 $f(X)\times f(X)$，也就是在所有 填写方案相同 的情况中，依次选出 两种连边方案的 方案数。

所以只要求出 同时考虑两种连边方案，满足它们的填写方案相同 的方案数。

考虑插头 DP。

$f_{i,j,p,q}$ 表示DP 到格子 $(i,j)$，两种连边方案的状压表示分别为 $p,q$ 的方案数。

对于一种连边方案，它的状压表示包括 最后 $m$ 个格子中每个格子是否向下连边 以及 这个格子是否向右连边，共 $m+1$ 位信息。

转移时先枚举前一个格子的状态，然后枚举这一位填写的数。

最好预处理一些信息优化转移，例如对每种连边方案预处理出在当前格子填每种数时可能的后继状态。

另外，注意数组要滚存。

1.png

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=75,M=8,P=998244353;
int T,n,m,a[N][M],Ans,dp[2][(1<<7)+5][(1<<7)+5],C;
I void go(int& x,CI y){(x+=y)>=P&&(x-=P,0);}
int main(){
    freopen("grid.in","r",stdin),freopen("grid.out","w",stdout);
    RI i,j,k,s1,s2,t1,t2,o1,o2,p,S=0;read(T);W(T--){
        for(read(n,m),C=(1<<m+1),i=1;i<=n;i++) for(j=1;j<=m;j++) read(a[i][j]);
        for(memset(dp,0,sizeof(dp)),dp[S=0][0][0]=1,i=1;i<=n;i++) for(j=1;j<=m;j++) for(S^=1,memset(dp[S],0,sizeof(dp[S])),k=(~a[i][j]?a[i][j]:0);k<=(~a[i][j]?a[i][j]:4);k++)
        for(s1=0;s1<C;s1++) if(p=k-(s1&1)-(s1>>j&1),0<=p&&p<=2) for(t1=t2=s1&(C-2)&(C-(1<<j)-1),!p?t2=C:p&1?t1^=1,t2^=1<<j:(t1^=1+(1<<j),t2=C),s2=0;s2<C;s2++) if(j>1(!(s1&1)&&!(s2&1)))
        if(p=k-(s2&1)-(s2>>j&1),0<=p&&p<=2) o1=o2=s2&(C-2)&(C-(1<<j)-1),!p?o2=C:p&1?o1^=1,o2^=1<<j:(o1^=1+(1<<j),o2=C),t1<C&&o1<C&&(go(dp[S][t1][o1],dp[S^1][s1][s2]),0),t1<C&&o2<C&&(go(dp[S][t1][o2],dp[S^1][s1][s2]),0),t2<C&&o1<C&&(go(dp[S][t2][o1],dp[S^1][s1][s2]),0),t2<C&&o2<C&&(go(dp[S][t2][o2],dp[S^1][s1][s2]),0);
        writeln(dp[S][0][0]);
    }return clear(),0;
}