题解（求求赞！！）

若n=m时，考虑如下性质：

假设点A指向了其下方的点B，那么其右方的点C的前驱就只能是其上方的点。
所以，矩阵的每一条副对角线（左下-右上）上的元素方向应当相同
因此每种方案实际上是一个循环的向右/向下的操作序列
我们现在已经有O（2^n）次方算法了

考虑n=m时，我们枚举了一种方案后，打表分析后发现：

假设有x个向下的操作，N−x个向右操作，当且仅当x⊥N，操作序列合法。
试着口胡证明一下：

n=m时

1+k*x % n

1+k*(n-x) % n

如果不互质，那有些位置永远不会碰到。

必要性证明完毕，充分性 毛想想 很显然。

因此答案为

​

考虑N≠M,令d=gcd(n,m)

可以发现每个d∗d的正方形内部的方向排布是一样的，感性证明比较显然，大家画画图就知道了。

答案为

考虑100%数据：

考虑转化问题：碰到障碍前走的路程=碰到每个障碍时走的路程的最小值。
那么问题就变成了如何计算碰到每个障碍时走的路程的最小值。

考虑dp[i][j][k]表示在（i，j）上，碰到障碍时走的路程的最小值为k的方案数。

由于每个d∗d的正方形内部的方向排布是一样的，枚举有i个向下的操作，j=d-i个向右操作，首先要满足上文中的限制:[i⊥d]∗[i⊥n]∗[j⊥m]。

若不考虑障碍，从(x,y)出发，经过d步后，我们必然会走到(i+x,j+y)。

也就是说路线被固定住了！

所以只要在[1i+1][1j+1]中dp就好了。

记格子(x,y)(1≤x≤i+1,1≤y≤j+1)的权值为走到有障碍的格子(x+k∗i,y+k∗j)(k∈N)的最小步数。

dp[i][j][k]的转移很显然，向dp[i+1][j][min(k,(i+1,j)的权值)]和dp[i][j+1][min(k,(i,j+1)的权值)]转移。

具体的可以看代码，觉得比我讲的清晰多了……

#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int mod=998244353;
int i,j,k;
char c=' ';
int n,m;
int opt,T;
int mp[maxn][maxn],f[maxn][maxn];
int dp[maxn][maxn][maxnmaxn];
int x,y,d,tx,ty,w,ans;
int read(){
int tot=0,fh=1;
char c=getchar();
while ((c<'0')||(c>'9')){ if(c=='-') fh=-1; c=getchar(); }
while ((c>='0')&&(c<='9')){ tot=tot10+c-'0'; c=getchar(); }
return totfh;
}
int gcd(int x,int y){
if (y0) return x;
return gcd(y,x%y);
}
int main(){
T=read();
for (opt=1;opt<=T;opt++){
n=read(); m=read(); d=gcd(n,m); ans=0;
if ((n1)&&(m1)){ printf("1\n"); continue; }
for (i=1;i<=n;i++){
while ((c<'0')||(c>'9')){ c=getchar(); }
for (j=1;j<=m;j++){
mp[i][j]=c-'0';
c=getchar();
}
}
for (x=0;x<=d;x++){
y=d-x;
if (((x0)&&(n1))||((y0)&&(m==1))||((gcd(x,d)==1)&&(gcd(y,d)==1)&&(gcd(x,n)==1)&&(gcd(y,m)==1))){
for (i=1;i<=x+1;i++){
for (j=1;j<=y+1;j++){
tx=i; ty=j; w=(i-1)+(j-1);
f[i][j]=nm;
for (k=1;k<=nm/d;k++){
if (mp[tx][ty]==1){
f[i][j]=min(f[i][j],w);
break;
}
tx=tx+x; ty=ty+y; w=w+d;
if (tx>n) tx=tx-n;
if (ty>m) ty=ty-m;
}
}
}
memset(dp,0,sizeof(dp)); dp[1][1][f[1][1]]=1;
for (i=1;i<=x+1;i++){
for (j=1;j<=y+1;j++){
for (k=1;k<=nm;k++){
if (i+1<=x+1) dp[i+1][j][min(k,f[i+1][j])]=(dp[i+1][j][min(k,f[i+1][j])]+dp[i][j][k])%mod;
if (j+1<=y+1) dp[i][j+1][min(k,f[i][j+1])]=(dp[i][j+1][min(k,f[i][j+1])]+dp[i][j][k])%mod;
}
}
}
for (i=1;i<=n*m;i++){
ans=(ans+(long long)dp[x+1][y+1][i]*i)%mod;
}
}
}
printf("%d\n",ans);
}
return 0;
}