2026牛客暑期多校联赛第三场F题赛后补题记录-拓冰建站

题目大意

给定一个n×mn×mn×m的网格。你需要在每个格子中填入0、1、20、1、20、1、2中的一个整数。
如果任意两个共享一条边的格子填有不同的整数，则称该填法为好的。
输出好的填法数对998244353998244353998244353取模的结果。
nnn和mmm(1≤n<10，1≤m<998244353)(1≤n<10，1≤m<998244353)(1≤n<10，1≤m<998244353)。

初步思路

首先观察到本题如果使用线性dpdpdp进行求解mmm的范围实在太大无法在规定时间内求解但是注意到nnn和mmm的数据量差异巨大因此想到可以使用矩阵快速幂状压dpdpdp从而求解

具体思路

因为nnn的范围极小因此可以按照一列一列进行处理数据从而dpdpdp但由于3∗2n−13*2^{n-1}3∗2n−1在n=9n=9n=9时过大无法使用矩阵快速幂进行优化因此考虑对每一种的数字排布进行状态压缩
可以先打表打出n=3n=3n=3时每一列的状态都有哪些(~~这里地方太小了列不下~~) 观察发现所有的数字排布总是遵循ABA或ABC的形式进一步思考我们可以发现n>3n>3n>3时所有数字的排布会以p[i]=p[i−2]和p[i]!=p[i−2]p[i]=p[i-2]和p[i]!=p[i-2]p[i]=p[i−2]和p[i]!=p[i−2]区分开来因此我们可以将数字的分布状态按照分布规律进行状态压缩最后可以使得当n=9n=9n=9时矩阵的大小不超过160021600^216002可以进行矩阵快速幂（矩阵为MMM）
在确认状态压缩后即可开始分析每一种状态如何从不同状态间转移由于每一种状态的具体排布之间的转移和状态间的转移总是相同我们可以把所有的状态都抽出来一个具体排布和其他类型的所有排布进行比较记录能够转移的具体状态数然后由状态转移方程dp[i]=dp[i−1]×Mdp[i]=dp[i-1]×Mdp[i]=dp[i−1]×M不难发现每一次转移实际上等同于矩阵进行多次乘法因此我们可以使用矩阵快速幂来进行优化
令adp=dp×Mm−1adp=dp×M^{m-1}adp=dp×Mm−1最后统计adpadpadp的所有状态此时的状态数输出即可

总结

这题好难啊好难好难啊以前根本没有接触过矩阵快速幂很少接触状压dp 因此赛时根本没有看出一点眉目费了牛鼻子劲打表后发现根本找不出规律赛后疯狂学习最后耗时4h左右终于ac这题呜呜呜呜呜呜呜呜呜

代码展示

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'intlen,mod=998244353,n,m,dp[2000500];queue<deque<int>>q[1050];structmatrix{intc[150][150];matrix(){for(inti=1;i<=len;i++)for(intj=1;j<=len;j++)c[i][j]=0;}voidprint(){for(inti=1;i<=len;i++){for(intj=1;j<=len;j++)cout<<c[i][j]<<" ";cout<<endl;}}}M;matrixoperator*(constmatrix&x,constmatrix&y){matrix temp;for(inti=1;i<=len;i++)for(intj=1;j<=len;j++)for(intk=1;k<=len;k++)temp.c[i][j]=(temp.c[i][j]+x.c[i][k]*y.c[k][j])%mod;returntemp;}matrixquickpow1(matrix a,intk){matrix res;for(inti=1;i<=len;i++)res.c[i][i]=1;while(k){if(k&1)res=res*a;a=a*a;k>>=1;}returnres;}intquickpow2(inta,intk){intres=1;while(k){if(k&1)res=(res%mod*a%mod)%mod;a=(a*a)%mod;k>>=1;}returnres;}voiddfs(intnow,intlast,deque<int>dq){if(now==n+1){intres=0;// cout << dq[0] << " " << dq[1] << " ";for(inti=2;i<n;i++){if(dq[i-2]==dq[i])res+=(1LL<<(i-2));// cout << dq[i] << " ";}// cout << endl;q[res].push(dq);return;}for(inti=0;i<=2;i++)if(i!=last){dq.push_back(i);dfs(now+1,i,dq);dq.pop_back();}}voidsolve(){for(inti=0;i<len;i++)for(intj=0;j<len;j++){autot=q[i].front();intneed=0;queue<deque<int>>tt;while(q[j].size()){autotemp=q[j].front();tt.push(temp);q[j].pop();intsz=temp.size();boolflag=false;for(intk=0;k<sz;k++)if(temp[k]==t[k]){flag=true;break;}if(!flag)need++;}M.c[i+1][j+1]=need;while(tt.size()){autotemp=tt.front();tt.pop();q[j].push(temp);}}// M.print();intsz=q[0].size();for(inti=1;i<=len;i++)dp[i]=sz;matrix temp=quickpow1(M,m-1);intans=0,adp[2000]={0};for(inti=1;i<=len;i++){for(intj=1;j<=len;j++)adp[i]=(adp[i]%mod+dp[j]*temp.c[j][i]%mod)%mod;ans=(ans%mod+adp[i]%mod)%mod;}cout<<ans;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;if(n==1)cout<<3*quickpow2(2,m-1)%mod;elseif(n==2)cout<<(2*quickpow2(3,m)%mod)%mod;else{len=1LL<<(n-2);deque<int>temp;dfs(1,-1,temp);solve();}return0;}