吉爷爷可真是一位神仙...
看到题目毫无思路，发现题目限制和条件较多，让我们先坐下来数一数条件，推一推结论。
机器人行走要求：
1.机器人只能向右或向下。
2.机器人走到边界后会回到行/列坐标为1的地方。
3.要求机器人走过每一个点且仅走一次。
4.是先规定好了机器人的每一种行走路线，再放的障碍物。
1.从左下到右上直线上机器人的行走方向相同。
这是最基本的一条结论，我们观察一下对于 ((i+1,j)) 和 ((i,j+1)) 这两个点，倘若在这两个点走的方向不一样，那么 ((i+1,j+1)) 这个点要么走不到，要么会走两遍，都不符合题意。
2.机器人行动的循环节是 (gcd(n,m)) 。
我们从左下向右上画出每一条对角线（注意还有右下角），一共有(n+m)条，将方向一样的用一种颜色涂上，一种颜色会涂 (displaystyle frac{lcm(n+m,n)}{n}) 条线，一共就需要 (displaystyle frac {n+m} { frac{lcm(n+m,n)}{n}}=gcd(n,m)) 种颜色，也就是循环节的长度。
3.设在一个循环节里机器人向下走了 (dx) 步，向右走了 (dy) 步，机器人的行走方案合法当且仅当 (gcd(dx,n)=1,gcd(dy,m)=1,gcd(dx,dy)=1) 。
前两个用裴蜀定理很好解释，对于第三个，我们设 (d=gcd(n,m)) ,那么 (dx+dy=d) ,因为 (gcd(dx,n)=1) ,所以 (gcd(dx,d)=1) ,所以 (gcd(dx,dy)=1) 。
因为 (n) 比较小，暴力枚举一下 (dx) 就行啦。
DP设 (val[x][y]) 为按照 (dx,dy) 走，最早什么时候撞上障碍物，含义就是只要经过了 ((x,y)) ，那么在第 (val[x][y]) 步一定会撞上障碍物。
设 (f[i][j][k]) 为从起点到 ((i,j)) 的所有路径中，路上最小的 (val) 是 (k) 的方案数，因为我们确定了前 (d) 步整张地图的行走方案就确定下来了，所以我们只用DP到 ((dx+1,dy+1)) (注意我们的起点是 ((1,1)) ).最后求一下方案数*val之和就行了。
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int T, n, m, d, ans, x, y;
const int N = 52, mod = 998244353;
int val[N][N], f[N][N][N * N];
char mp[N][N];
int work(int x) {return x >= mod ? x - mod : x;}
int GCD(int x, int y) {return y ? GCD(y, x % y) : x;}
int DP(int dx, int dy)
{
for (int i = 1; i <= dx + 1; ++i)
for (int j = 1; j <= dy + 1; ++j)
for (int k = 1; k <= n * m; ++k)f[i][j][k] = 0;
f[1][1][val[1][1]] = 1;
for (int i = 1; i <= dx + 1; ++i)
for (int j = 1; j <= dy + 1; ++j)
for (int k = 1; k <= n * m; ++k)
{
if (!f[i][j][k])continue;
int &t1 = f[i + 1][j][min(k, val[i + 1][j])], &t2 = f[i][j + 1][min(k, val[i][j + 1])];
if (i <= dx)t1 = work(t1 + f[i][j][k]);
if (j <= dy)t2 = work(t2 + f[i][j][k]);
}
int res = 0;
for (int i = 1; i <= n * m; ++i)res = work(res + (LL)i * f[dx + 1][dy + 1][i] % mod);
return res;
}
int main()
{
cin >> T;
while (T--)
{
scanf("%d%d", &n, &m); d = GCD(n, m); ans = 0;
for (int i = 1; i <= n; ++i)scanf("%s", mp[i] + 1);
for (int dx = 0, dy; dx <= d; ++dx)
{
dy = d - dx;
if (GCD(dx, dy) != 1 || GCD(dx, n) != 1 || GCD(dy, m) != 1)continue;
for (int x = 1; x <= dx + 1; ++x)
for (int y = 1; y <= dy + 1; ++y)
{
int tx = x, ty = y, w = x + y - 2; val[x][y] = n * m;
do
{
if (mp[tx][ty] == '1') {val[x][y] = w; break;}
tx += dx, ty += dy, w += d;
if (tx > n)tx -= n; if (ty > m)ty -= m;
} while (tx != x || ty != y);
}
ans = work(ans + DP(dx, dy));
}
cout << ans << "
";
}
return 0;
}