题目翻译

有一个 $H\times W$ 的国际象棋棋盘，求一个车从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ 正好用 $K$ 步的方案数。

题目思路

首先看到题，很显然是动态规划。$f_{k,i,j}$ 表示走到 $(i,j)$ 正好 $k$ 步的方案。但时间复杂度过高，考虑进行优化。

我们可以不记录具体走到哪个点位，我们只需知道当前在不在起点即可。于是就有 $f_{k,0/1/2/3}$ 表示第 $k$ 步时，当前位置为 $(x_1,y_1),(x_1,非y_1),(非x_1,y_1),(非x_1,非y_1)$。

我们在运用一些排列组合的基本知识，便能得到以下转移方程：

$$
f_{k,0} = f_{k-1,1} \times (W-1) + f_{k,2} \times (H-1)
$$

$$
f_{k,1} = f_{k-1,1} \times (W-2) + f_{k,0} + f_{k,3} \times (H-1)
$$

$$
f_{k,2} = f_{k-1,2} \times (H-2) + f_{k,0} + f_{k,3} \times (W-1)
$$

$$
f_{k,3} = f_{k-1,3} \times (H+W-4) + f_{k,2} + f_{k,1}
$$

接着，我们再循环过程中是可以压掉第一维 $k$ 的，那么我们只需记录 $4$ 个变量即可。

完整代码

远古时期代码，码风有点不好请见谅。

#include<bits/stdc++.h>
#define ll long long
#define p 998244353
using namespace std;
long long a,b,c,d;
int main()
{
    ll h,w,k,xx1,xx2,yy1,yy2;
    cin>>h>>w>>k>>xx1>>yy1>>xx2>>yy2;
    a=1;
    for(int i=0;i<k;i++)
    {
        ll a1,b1,c1,d1;
        a1=b*(w-1)+c*(h-1);
        b1=b*(w-2)+a+d*(h-1);
        c1=c*(h-2)+a+d*(w-1);
        d1=d*(h+w-4)+b+c;
        a1%=p;
        b1%=p;
        c1%=p;
        d1%=p;
        a=a1;
        b=b1;
        c=c1;
        d=d1;
    }
    if(xx2==xx1&&yy2==yy1)cout<<a%p;
    else if(xx2==xx1)cout<<b%p;
    else if(yy2==yy1)cout<<c%p;
    else cout<<d%p;
    return 0;
}