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;}