如何建立一个自己的网站?,中山蓝图科技网站建设,企业官网制作公司,东方商城网正题 题目大意
给出nmn\times mnm的网格填着−1∼4-1\sim 4−1∼4的数字#xff0c;对于将所有的−1-1−1填上0∼40\sim 40∼4的方案中#xff0c;定义方案XXX的权值#xff0c;设在相邻网格之间连线#xff08;每对只能连一条#xff09;使得每个网格连出去的边数恰好位…正题 题目大意
给出n×mn\times mn×m的网格填着−1∼4-1\sim 4−1∼4的数字对于将所有的−1-1−1填上0∼40\sim 40∼4的方案中定义方案XXX的权值设在相邻网格之间连线每对只能连一条使得每个网格连出去的边数恰好位数字的方案数为f(X)f(X)f(X)那么权值为f2(X)f^2(X)f2(X)。
求所有方案的权值和对998244353998244353998244353取模。
1≤T≤10,1≤n≤70,1≤m≤61\leq T\leq 10,1\leq n\leq 70,1\leq m\leq 61≤T≤10,1≤n≤70,1≤m≤6 解题思路
主要的难点在这个平方处我们有道经典处理方案数平方的例题[NOI2009]管道取珠做法就是同时维护两个共线推进的方案这样每对方案之间都有贡献方案数就平方了。
但是这样的状态也是平方的我们需要考虑压缩一下状态正常来说的插头dpdpdp可能是O(5m)O(5^m)O(5m)的状态但是注意到每队网格只能连一条边所以对于每个块最多只能剩下插头数的状态也就是除了当且枚举快左边那个以外都是222个状态这样状态就很少了只有969696种直接平方做然后插头dpdpdp转移即可。 code
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int P998244353;
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|((p1)m)|((p0)j);}
void work(int g,int sq,int sp,int w){int S(sqm1)|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 g0,MS(1m1)-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 i0;in;i){for(int j0,lim;jm;j){scanf(%d,lim);g^1;for(int p0;pl[g];p)v[g][s[g][p]]f[g][s[g][p]]0;l[g]0;for(int x0;x4;x){if(lim!-1lim!x)continue;for(int p0;pl[!g];p){int Ss[!g][p],zqx,zpx;int sqSm1,spS-(sqm1);int kq(j?((sqj-1)1):0),kp(j?((spj-1)1):0);zq-((sqm)1)((sqj)1);kq-((sqm)1);zp-((spm)1)((spj)1);kp-((spm)1);if(zq0||zp0)continue;sqMS^(1m)^(1j);spMS^(1m)^(1j);for(int rq0;rqkq;rq)for(int rp0;rpkp;rp){if(zqrq||zprp||zq-rq2||zp-rp2)continue;work(g,ges(sq^(rqj-1),j,zq-rq),ges(sp^(rpj-1),j,zp-rp),f[!g][S]);}}}}g^1;for(int p0;pl[g];p)v[g][s[g][p]]f[g][s[g][p]]0;l[g]0;for(int p0;pl[!g];p){int Ss[!g][p];int sqSm1,spS-(sqm1);if(((sqm)1)|((spm)1))continue;work(g,sq,sp,f[!g][S]);}}printf(%d\n,f[g][0]);}return 0;
}
