题解 P1002 【过河卒】

为什么大家写的全是递推！！！ 我一定要写一篇不是递推的题解！！！ **Updated on 2022.7.14：添加 $\LaTeX$。** --- 这里我介绍两种方法。 ### 矩阵乘法 由于数据很小，$n$ 和 $m$ 的规模只有 $20$，所以允许一些复杂度较大的做法通过。 如果我们给网格图内的点标号，记从 $i$ 号点到达 $j$ 号点的方法数为 $f(i,j)$，$i$ 号点到 $j$ 号点的边的条数为 $a(i,j)(a(i,j)\in \{0,1\})$，那么枚举经过的点 $k$，则有 $i$ 点到 $j$ 点的方法数 $=i$ 点到 $k$ 点的方法数 $\times k$ 点到 $j$ 点的方法数，形式化的讲，$f(i,j)=f(i,k)\cdot a(k,j)$。 我们惊奇的发现，这就是矩阵乘法的定义。 因此，我们连接所有互相可达的点，进行矩阵快速幂即可。 ```cpp #include <bits/stdc++.h> #define ll long long #define rint register int using namespace std; int a[22][22][22][22]; ll tot[22][22][22][22]; int n,m,x,y; int judge(int p,int q)//判断p,q是否可走 { if(p==x && q==y) return 0; int px=abs(p-x); int qy=abs(q-y); int mi=min(px,qy); int mx=max(px,qy); if(mi==1 && mx==2) return 0; return 1; } ll tmp[22][22][22][22]={0}; void ta()//将tot乘上a { for(int i1=0;i1<=n;i1++) for(int i2=0;i2<=m;i2++) for(int j1=i1;j1<=n;j1++)//如果j在i号点左侧，答案必然为0 for(int j2=i2;j2<=m;j2++)//同理 for(int k1=i1;k1<=j1;k1++)//k点必然在i和j之间 for(int k2=i2;k2<=j2;k2++) tmp[i1][i2][j1][j2]+=tot[i1][i2][k1][k2]*a[k1][k2][j1][j2]; memcpy(tot,tmp,sizeof tmp);//复制回去 } void tt()//将tot平方 { for(int i1=0;i1<=n;i1++) for(int i2=0;i2<=m;i2++) for(int j1=i1;j1<=n;j1++) for(int j2=i2;j2<=m;j2++) for(int k1=i1;k1<=j1;k1++) for(int k2=i2;k2<=j2;k2++) tmp[i1][i2][j1][j2]+=tot[i1][i2][k1][k2]*tot[k1][k2][j1][j2]; memcpy(tot,tmp,sizeof tmp); } void pw(int ci)//求a的ci次方 { if(ci==0) return; pw(ci>>1); tt(); if(ci&1) ta(); } int main() { cin>>n>>m>>x>>y; //连接竖向边 for(int i=0;i<n;i++) for(int j=0;j<=m;j++) if(judge(i,j)) a[i][j][i+1][j]=1; //连接横向边 for(int i=0;i<=n;i++) for(int j=0;j<m;j++) if(judge(i,j)) a[i][j][i][j+1]=1; //矩阵的单位元 for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) tot[i][j][i][j]=1; pw(n+m);//由于要走的步数是一定的，所以就是a^(n+m) cout<<tot[0][0][n][m]; return 0; } ``` ### 小学奥数 前置芝士： 1. 从 $(0,0)$ 走到 $(m,n)$ 的最短路数量=$C^m_{m+n}$ 2. 从 $(0,0)$ 经过 $(x,y)$ 到达 $(m,n)$ 的最短路数量=$C^x_{x+y}C^{m-x}_{m+n-x-y}$（即芝士 1 配合乘法原理的结果） 如果您了解了上面的内容，那么我们就先以样例画一张图： |0|1|2|3|4|5|6| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |S|.|.|.|.|.|.| |.|.|x|.|x|_|.| |.|x|.|.|_|x|.| |.|.|.|_x|.|.|.| |.|x|_|.|.|x|.| |.|_|x|.|x|.|.| |.|.|.|.|.|.|E| `x` 表示不可以走的地方。 我们分情况讨论。 #### 1.不经过特殊格子的 我们称下划线所在的格子为特殊格子。显然这五个格子最多经过1个，所以我们只要求出总共的方法数-经过这五个格子的方法数即可求出。也就是求$C^n_{n+m}-\sum^{2}_{i=-2}C^{x-i}_{x+y}C^{n-x+i}_{n+m-x-y}$. #### 2.经过 $(x-2,y+2)$ 的 这种路径只有一种情况：先到达 $(x-3,y+2)$，向右一格，向下一格到达 $(x-2,y+3)$，然后走到 $(m,n)$。 方法数为$C^{x+2}_{x+y-1}C^{n-x-3}_{n+m-x-y-1}$。 #### 3.经过 $(x+2,y-2)$ 的 同理，方法数为$C^{x-3}_{x+y-1}C^{n-x+2}_{n+m-x-y-1}$。 #### 4.经过 $(x-1,y+1)$ 的 要经过这个点，需要从 $(x-3,y)$ 进入马的攻击范围，右2步，下，右，下2步到达 $(x,y+3)$，然后走到 $(m,n)$。 到达 $(x-3,y)$ 的方案数为 $C^x_{x+y-3}$，从 $(x,y+3)$ 到终点的方案数为 $C^{n-x-3}_{n+m-x-y-3}$。 #### 5.经过 $(x+1,y-1)$ 的 与第 4 种情况同理，方案数为 $C^{x-3}_{x+y-3}C^{n-x}_{n+m-x-y-3}$。 完结撒花！！！ 等等，感觉有点问题... 有一种特殊情况：如果起点或终点离马的位置太近，那么上面的分类讨论的第 4 种和第 5 种情况就会出现问题——可能起点或终点本来就在马的攻击范围内。 所以，遇到这种情况别忘记特判。 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; ll C(int m,int n) { if(n<0 || m<0 || n<m) return 0; ll tot=1; for(int i=1;i<=m;i++) { tot*=n-i+1; tot/=i; } return tot; } int n,m,x,y; int rt[5][5]={ 0,0,1,0,0, 0,0,1,1,0, 0,0,0,1,1};//我们记录下哪些节点作为起点时，可以从右边的口子出去，其中(2,2)为马的位置 int dw[5][5]={ {}, {}, 1,1,0,0,0, 0,1,1,0,0, 0,0,1,0,0};//同理，哪些可以从下边口子出去 int main() { cin>>n>>m>>x>>y; if(n-x<3 && m-y<3) { x=n-x; y=m-y; }//为了不想把特判代码写两遍，如果终点离得太近就旋转180度，变成起点离得太近的情况 if(x<3 && y<3) { int nx=2-x; int ny=2-y;//起点相对于马的坐标而言的位置 ll tot=0; tot+=C(n-x,m+n-x-y-3)*rt[nx][ny];//右边出去的方法数 tot+=C(n-x-3,m+n-x-y-3)*dw[nx][ny];//同理 cout<<tot; return 0; } ll tot=C(n,n+m); for(int i=-2;i<=2;i++) tot-=C(x-i,x+y)*C(n-x+i,n+m-x-y); //情况1 tot+=C(x+2,x+y-1)*C(n-x-3,n+m-x-y-1);//情况2 tot+=C(x-3,x+y-1)*C(n-x+2,n+m-x-y-1);//情况3 tot+=C(x,x+y-3)*C(n-x-3,n+m-x-y-3);//情况4 tot+=C(x-3,x+y-3)*C(n-x,n+m-x-y-3);//情况5 cout<<tot; return 0; } ``` 完结撒花！！！