题解 P1002 【过河卒】

yummy · 2019-08-26 16:02:19 · 题解

为什么大家写的全是递推！！！

我一定要写一篇不是递推的题解！！！

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)。

我们惊奇的发现，这就是矩阵乘法的定义。

因此，我们连接所有互相可达的点，进行矩阵快速幂即可。

#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 配合乘法原理的结果）

如果您了解了上面的内容，那么我们就先以样例画一张图：

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 种情况就会出现问题——可能起点或终点本来就在马的攻击范围内。

所以，遇到这种情况别忘记特判。

#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;
}

完结撒花！！！