题目描述
一个\(n\times m\)的网格，有一个机器人一开始在\((1,1)\)，每次机器人可以向右或向下走一步，\((i,m)\)的右边是\((i,1)\),\((n,j)\)的下边是\((1,j)\)，机器人需要不重不漏地走完所有格子回到\((1,1)\)。
现在给出若干障碍，对于每一个上述行走方案，走到障碍时会停止，求所有方案的行走的格子的个数和。
解题思路
首先考虑什么样的方案是合法的。
- 性质一：对于一个格子\((i,j)\)，\((i-1,j)\)和\((i,j-1)\)的行走方向必须是一样的，否则，要么\((i,j)\)会走两次，要么走不到\((i,j)\)
推论：每条副对角线的方向是一样的
- 性质二：第\(i\)条副对角线的方向和第\(i+gcd(n,m)\)条的方向是一样的
证明：
把性质一推广到模意义下，副对角线也推广到模意义下，那么\((i,m)\)和\((i-1,1)\)方向应该是一样的，也就是第\(i+m-1\)条对角线和第\(i-1\)条对角线方向一样，也就是差为\(m\)的对角线方向一样，同理可得差为\(n\)的对角线也一样，那么量条对角线\(x,y\)方向一样当且仅当存在\(a,b\)使得\(x+an+bm=y\)，也就是\(an+bm=(y-x)\)，由裴蜀定理，该式成立当且仅当\(gcd(n,m)|(y-x)\)，也就是说x和\(x+gcd(n,m)\)方向一样。
推论：如果把行走的方向看成一个序列，则序列存在一个循环节是\(\gcd(n,m)\)，原因是每一步必定会到下一个对角线，所以该序列和对角线是一样的。
设在一个循环节中向下走了\(dx\)步，向右走了\(dy\)步，即\(dx+dy=gcd(n,m)\)
那么横坐标回到\(1\)需要经过\(\frac{lcm(dx,n)}{dx}\)个循环节，纵坐标回到\(1\)需要经过\(\frac{lcm(dy,m)}{dy}\)个循环节，两个坐标都回到1需要\(lcm(\frac{lcm(dx,n)}{dx},\frac{lcm(dy,m)}{dy})\)个循环节，而总共有\(\frac{nm}{gcd(n,m)}\)个循环节。
也就是说，我们要让
\[lcm(\frac{lcm(dx,n)}{dx},\frac{lcm(dy,m)}{dy})=\frac{nm}{gcd(n,m)} \]\[lcm(\frac{n}{gcd(dx,n)},\frac{m}{gcd(dy,m)})=lcm(n,m) \]对一个质因子\(p\)，及其在\(n,m\)的指数\(c1,c2\)，讨论：
- \(min(c1,c2)=0\)
若\(p|gcd(dx,n)\)，则\(c1>0\)，那么左式一定会比比右式在p的指数上少，所以\(p\nmid gcd(dx,n)\)，同理\(p \nmid gcd(dy,m)\)。
- \(min(c1,c2)>0\)
若\(p\mid gcd(dx,n)\)，则\(p|gcd(n,m)-dx\)即\(p|dy\)，即\(p|gcd(dy,m)\)，所以左边还是一定比右边少指数，所以\(p\nmid gcd(dx,n),gcd(dy,m)\)
综上所述 ，\(p\nmid gcd(dx,n),gcd(dy,m)\).
即\(gcd(dx,n)=gcd(dy,m)=1\)，易得这是路径合法的充要条件。
因此可以枚举合法的\(dx\)。
计算答案时，考虑枚举撞到障碍的轮数，以及撞到的障碍，因为有循环节，所以所有循环节里州的路线是一样的，也就是说，如果第一轮走到了\((x,y)\)这个点，那么之后所有循环节里到这个位置时都必须能走。
方便起见，我们可以把所有循环节的障碍重叠起来，设前\(i\)个循环的障碍重叠起来得到的图是\(G^i\)
那么我们在第\(c\)轮撞到\((x,y)\)的充要条件是：
1.该路线在\(G^{c-1}\)可以从左上走到右下。
2.该路线在\(G^c\)可以从左上走到\((x-1,y)\)或\((x,y-1)\)。
这又等价于：
1.该路线在\(G^c\)可以从左上走到\((x-1,y)\)或\((x,y-1)\)。
2.该路线在\(G^{c-1}\)可以从\((x,y)\)走到右下。
因此我们只需要知道在\(G^c\)或\(G^{c-1}\)中从左上走到某个点，或从某个点走到右下的方案数即可，显然可以\(O(nm)\)dp出来。
因此总的复杂度是\(O(Tn^4)\)，显然没有一维能够跑满，所以可以轻松通过。
#include<bits/stdc++.h>
using namespace std;
const int N =55;
const int mod = 998244353;
char s[N][N];
int f[N][N],g[N][N];
int gcd(int a,int b)
{
if(!b)return a;
return gcd(b,a%b);
}
int ans=0;
bool A[N][N],B[N][N];
void get(int n,int m)
{
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
f[i][j]=g[i][j]=0;
f[1][1]=(A[1][1]==0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if((i==1&&j==1)||A[i][j])continue;
f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
}
g[n][m]=(B[n][m]==0);
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
{
if((i==n&&j==m)||B[i][j])continue;
g[i][j]=(g[i+1][j]+g[i][j+1])%mod;
}
}
#define R(x) (x%m+1)
#define D(x) (x%n+1)
int n,m;
void solve()
{
ans=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
int d=gcd(n,m),C=n*m/d;
for(int dx=0;dx<=d;dx++)
if(gcd(dx,n)==1&&gcd(d-dx,m)==1)
{
int dy=d-dx;
for(int i=1;i<=dx+1;i++)
for(int j=1;j<=dy+1;j++)
A[i][j]=B[i][j]=0;
int x=1,y=1;
for(int c=1;c<=C;c++)
{
for(int i=x,a=1;a<=dx+1;i=D(i),a++)
for(int j=y,b=1;b<=dy+1;j=R(j),b++)
A[a][b]|=(s[i][j]=='1');
get(dx+1,dy+1);
for(int i=x,a=1;a<=dx+1;i=D(i),a++)
for(int j=y,b=1;b<=dy+1;j=R(j),b++)
if(s[i][j]=='1')ans=(ans+1ll*((c-1)*(dx+dy)+a-1+b-1)%mod*(f[a-1][b]+f[a][b-1])%mod*g[a][b]%mod)%mod;
for(int i=x,a=1;a<=dx+1;i=D(i),a++)
for(int j=y,b=1;b<=dy+1;j=R(j),b++)
B[a][b]|=(s[i][j]=='1');
for(int a=1;a<=dx;x=D(x),a++);
for(int b=1;b<=dy;y=R(y),b++);
}
}
printf("%d\n",ans);
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}