\(19.3.25\)
规律就是
对于\(n=m\)我们每一条左下到右上的对角线上的点的走法都是一样的且每\(n\)步一个轮重复
对于\(n!=m\)我们找到最大公约数\(d\)，在每个\(d∗d\)的方格里满足左上到右下的对角线点的走法一样且\(d\)轮一个重复
然后枚举\(dx,dy=d−dx\)，我们要满足\(gcd(n,dx)==1且gcd(m,dy)==1\)这时是一个合法路径
显然有一些点是必须要经过的，我们把这些点遍历一遍，同时算出\(fir[i][j]\)表示向下走\(i\)和向右走\(j\)最早第几次走到障碍
然后我们进行一下\(dp\)，就是对于一个点\(i,j\)，要它恰好第\(k\)轮撞到障碍物的话，我们需要到达\((i,j)\)之前的点轮数都大于\(k\)，之后的点都大于等于\(k\)
然后对于每个\(fir[i][j]==k\)的点统计一下就好了
\(19.3.30\)
关于这道题的找规律 : 首先对于这种循环或者矩形上的操作可以先考虑正方形 ,
发现对于\(3*3\)的正方形一定是横竖分别走1步和2步才能回到原点 ;但这太小了
对于\(5*5\)的正方形除了\(1\)步和\(4\)步还有\(2\)步和\(3\)步 , 而\(4*4\)的正方形却不能是\(2\)步和\(2\)步
猜一个结论 : 必须是互质的 , 否则不兼容; 更细心还可以发现 , 循环的步数还必须是\(n\) ; 不然有些点就会走不到或者提前撞到 , 即不会走满
猜测正方形嵌套到长方形里面会怎么样 , 发现这时每个块里的线的形状都是一样的 .
为什么会这样呢 ? 也许这时正方形的排布也要满足长和宽互质 , 否则不兼容 .
只有互质的 , 才是兼容的 , 才能跑满跑完 .
所以要找到\(d=gcd(n,m)\) , 分成\(d*d\)的正方形去做
而对于循环内的顺序却是不重要的
然后就是\(DP\)了 , \(DP\)也很巧妙
在一组合法的循环方案中 , 设\(fir[x][y]\)表示\((x,y)\)这个点在第几轮会第一次撞到 ,
然后要统计第\(k\)轮撞到\((x,y)\)的方案数 , 考虑这个就可以只用看这个循环的正方形了
可以发现一条路径如果撞上\((x,y)\) , \((x,y)\)之前的经过点都必须满足\(fir[i][j]>fir[x][y]\) , 在\((x,y)\)之后的经过点都必须满足\(fir[i][j]>=fir[x][y]\)
从左上往右下 , 从右下往左上分别做\(DP\)就好了
\(19.4.4\)
枚举自己的状态 , 考虑前面和后面要满足的条件 , 参考[LnOI2019]加特林轮盘赌
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}
const int N=55;
const int mod=998244353;
int fir[N][N],f[N][N],g[N][N];
char s[N][N];
int n,m,P,T,ans;
inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
inline int mul(LL x,int y){x*=y;return x>=mod?x%mod:x;}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline int solve(){
n=read(),m=read(),P=gcd(n,m),T=n*m/P;
ans=0;
for(int i=0;i<n;i++) scanf("%s",s[i]);
for(int tx=0,ty=P;tx<=P;tx++,ty--) if(gcd(tx,n)==1&&gcd(ty,m)==1){
memset(fir,0x3f,sizeof fir);
for(int i=1,stx=0,sty=0;i<=T;i++,(stx+=tx)%=n,(sty+=ty)%=m){
for(int dx=0;dx<=tx;dx++) for(int dy=0;dy<=ty;dy++)
if(s[(stx+dx)%n][(sty+dy)%m]=='1') fir[dx][dy]=min(fir[dx][dy],i);
}
for(int t=1;t<=T;t++){
memset(f,0,sizeof f);memset(g,0,sizeof g);
f[0][0]=1,g[tx][ty]=1;
for(int i=0;i<=tx;i++)
for(int j=0;j<=ty;j++){
if(i&&fir[i-1][j]>t) f[i][j]=add(f[i][j],f[i-1][j]);
if(j&&fir[i][j-1]>t) f[i][j]=add(f[i][j],f[i][j-1]);
}
for(int i=tx;i>=0;i--)
for(int j=ty;j>=0;j--){
if(i<tx&&fir[i+1][j]>=t) g[i][j]=add(g[i][j],g[i+1][j]);
if(j<ty&&fir[i][j+1]>=t) g[i][j]=add(g[i][j],g[i][j+1]);
}
for(int i=0;i<=tx;i++){
for(int j=0;j<=ty;j++) if((i+j)>=0&&fir[i][j]==t)
ans=add(ans,mul((t-1)*P+i+j,mul(f[i][j],g[i][j])));
}
}
}
return ans;
}
int main(){
for(int i=read();i;i--) printf("%d\n",solve());
}