题解
- 需要先说明一点东西：
1
- 同一副对角线方向相同,共有$gcd(n,m)$条不同的副对角线，机器人的行为是一个$gcd(n,m)$的循环；；
- 如果左上方是$(1,1)$,容易看出所有的路径是从左或上面连向右或下面并且紧密排列，所以所有副对角线上方向相同；
- 有些副对角线是间隔开的只需要将网格重复几次，那么一条副对角的特征就可以用$x+y+kn+km$
- 由斐蜀定理可知一共有$gcd(n,m)$条；
- 并且每次一定是从一条对角线$x$走向对角线$x+1$,所以循环节为$gcd(n,m)$
2
- $n*m$的一种矩形，记$d=gcd(n,m)$，$d_{x}$为$d$步中向下走的步数，$d_{y}$为向右走的步数，一种方案合法当且仅当$$d_{x}+d_{y}=d$, gcd(d_{x},n)=gcd(d_{y},m)=1$$
2.1 充分性：
- 考虑一个格子在不同的循环节内的位置：$(x+kd_{x} , y+kd_{y})$
- 由于$gcd(d_{x},n)=gcd(d_{y},m)=1$，所以$x$的循环节长度是$n$,$y$的循环节长度是$m$，同时循环节内元素互不相同，所以$(x,y)$的循环节长度是$lcm(n,m)$
- 所以棋盘一定会被分成$\frac{nm}{lcm(n,m)} = gcd(n,m)$个类;
- 考虑在同一个循环节内的不同位置:$(x_{i},y_{i})$和$(x_{j},y_{j})$
- 记$\delta x = abs(x_{i}-x_{j}) , \delta y = abs(y_{i}-y_{j}) $
- 必有$\delta x < d_{x} \ || \ \delta y < d_{y} $发生，所以$(x_{i},y_{i})$和$(x_{j},y_{j})$一定不同类；
- 由于$d_{x}+d_{y}=d$，所以这就有了所以$d$个类即可以将棋盘完全覆盖；
2.2 必要性：
- 由斐蜀定理可知在任意$gcd$不为$1$的时候有些坐标是没法表示的，所以肯定也走不到；
- 现在可以求方案了，考虑如何求步数和：
- 枚举满足的$d_{x}$和$d_{y}$
- 枚举撞到障碍的轮数$l$，得到起点$(x_{l},y_{l})$；
- 可以将前$l$轮和前$l-1$的障碍全部分别映射到$(x_{l},y_{l}) , (x_{l}+d_{x}+1,y_{l}+d_{y}+1)$的矩形中；
- 现在需要找到每一条在前$l-1$轮不停下在$l$轮停下的路径；
- 枚举第$l$轮的障碍，前$l$轮图上从起点到最后一个非障碍点的路径 *前$l-1$图上 障碍点到终点的路径即可；
- 分别在出处理好的前$l$和前$l-1$的图上做两个普通路径计数$dp$即可；
- View Code
1 #include<bits/stdc++.h> 2 #define mod 998244353 3 using namespace std; 4 const int N=110; 5 int n,m,mp[2][N][N],f[2][N][N],ans; 6 char s[N][N]; 7 void upd(int&x,int y){x+=y;if(x>=mod)x-=mod;} 8 int gcd(int a,int b){return !b?a:gcd(b,a%b);} 9 int main(){10 ????#ifndef ONLINE_JUDGE11 ????freopen("T2.in","r",stdin);12 ????freopen("T2.out","w",stdout);13 ????#endif14 ????int T;scanf("%d",&T);15 ????while(T--){16 ????????ans=0;17 ????????scanf("%d%d",&n,&m);18 ????????for(int i=1;i<=n;++i)scanf("%s",s[i]+1); 19 ????????for(int i=1;i<=n<<1;++i)20 ????????for(int j=1;j<=m<<1;++j)s[i][j]=s[(i-1)%n+1][(j-1)%m+1];21 ????????int d=gcd(n,m),cur=0;22 ????????for(int dx=0,dy;dx<=d;++dx){23 ????????????dy=d-dx;24 ????????????if(gcd(dx,n)!=1||gcd(dy,m)!=1)continue; 25 ??????????????26 ????????????for(int i=1;i<=dx+1;++i)27 ????????????for(int j=1;j<=dy+1;++j)28 ????????????mp[0][i][j]=mp[1][i][j]=0;29 ??????????????30 ????????????for(int l=1,ax=1,ay=1;l<=n*m/d;++l){31 ??????????????????32 ????????????????cur^=1;33 ??????????????????34 ????????????????for(int i=1;i<=dx+1;++i)35 ????????????????for(int j=1;j<=dy+1;++j)36 ????????????????mp[cur][i][j]=mp[cur^1][i][j]|(s[ax+i-1][ay+j-1]-‘0‘);37 ??????????????????38 ????????????????for(int i=1;i<=dx+1;++i)39 ????????????????for(int j=1;j<=dy+1;++j)f[0][i][j]=f[1][i][j]=0;40 ??????????????????41 ????????????????if(!mp[cur][1][1]){42 ????????????????????f[cur][1][1]=1;43 ????????????????????for(int i=1;i<=dx+1;++i)44 ????????????????????for(int j=1;j<=dy+1;++j){45 ????????????????????????if(i!=dx+1&&!mp[cur][i+1][j])upd(f[cur][i+1][j],f[cur][i][j]); 46 ????????????????????????if(j!=dy+1&&!mp[cur][i][j+1])upd(f[cur][i][j+1],f[cur][i][j]);47 ????????????????????}48 ????????????????}49 ??????????????????50 ????????????????if(!mp[cur^1][dx+1][dy+1]){51 ????????????????????f[cur^1][dx+1][dy+1]=1;52 ????????????????????for(int i=dx+1;i;--i)53 ????????????????????for(int j=dy+1;j;--j){54 ????????????????????????if(i!=1&&!mp[cur^1][i-1][j])upd(f[cur^1][i-1][j],f[cur^1][i][j]);55 ????????????????????????if(j!=1&&!mp[cur^1][i][j-1])upd(f[cur^1][i][j-1],f[cur^1][i][j]);56 ????????????????????}57 ????????????????}58 ??????????????????59 ????????????????for(int i=1;i<=dx+1;++i)60 ????????????????for(int j=1;j<=dy+1;++j)if(mp[cur][i][j]){ 61 ????????????????????int x=0;62 ????????????????????if(i!=1)upd(x,f[cur][i-1][j]);63 ????????????????????if(j!=1)upd(x,f[cur][i][j-1]); 64 ????????????????????int y = f[cur^1][i][j];65 ????????????????????upd(ans, 1ll*((l-1)*d+i+j-2)*x%mod*y%mod);66 ????????????????}67 ??????????????????68 ????????????????ax=(ax+dx-1)%n+1,ay=(ay+dy-1)%m+1;69 ??????????????70 ????????????}71 ????????}72 ????????printf("%d\n",ans); 73 ????}74 ????return 0;75 }
LGP4588[JSOI2018]扫地机器人
原文地址：https://www.cnblogs.com/Paul-Guderian/p/10410347.html