题目链接
1 暴力解法
1.1 状态定义
d p [ k ] [ i ] [ j ] dp[k][i][j]dp[k][i][j]表示走k kk步到达第i ii行第j jj列的方案数。
1.2 状态转移方程
t = 0 时， d [ t ] [ x 1 ] [ y 1 ] = 1 , 其他初始化为 0 。 t=0时，d[t][x1][y1]=1,其他初始化为0。t=0时，d[t][x1][y1]=1,其他初始化为0。
t > = 1 时， d p [ t ] [ i ] [ j ] = Σ d p [ t − 1 ] [ x ] [ j ] ( 1 < = x < = n , x ≠ i ) + Σ d p [ t − 1 ] [ i ] [ y ] ( 1 < = y < = w , y ≠ j ) . t>=1时，dp[t][i][j]=Σdp[t-1][x][j](1<=x<=n,x≠i)+Σdp[t-1][i][y](1<=y<=w,y≠j).t>=1时，dp[t][i][j]=Σdp[t−1][x][j](1<=x<=n,x=i)+Σdp[t−1][i][y](1<=y<=w,y=j).
1.3 实现代码
#include<bits/stdc++.h>usingnamespacestd;constintmod=998244353;intdp[110][110][110];intmain(){intk,w,h,x1,x2,y1,y2;cin>>h>>w>>k;cin>>x1>>y1>>x2>>y2;dp[0][x1][y1]=1;for(intt=1;t<=k;t++){for(inti=1;i<=h;i++){for(intj=1;j<=w;j++){for(intx=1;x<=h;x++)if(x!=i)dp[t][i][j]=(dp[t][i][j]+dp[t-1][x][j])%mod;for(inty=1;y<=w;y++)if(y!=j)dp[t][i][j]=(dp[t][i][j]+dp[t-1][i][y])%mod;}}}cout<<dp[k][x2][y2];return0;}这道题数据规模：H，W都到了1e9，K也高达1e6，暴力解法不同通过全部数据。而且多重循环会超时。
2 一种AC的解法
2.1 解题思路
通过用暴力算法试了多个样例，我发现方案数最多只会出现4个值。
比如，k = 4 , h = 3 , w = 3 k=4,h=3,w=3k=4,h=3,w=3，从( 1 , 3 ) (1,3)(1,3)出发的走4步，第i ii行第j jj列方案数如下：
又如，k = 5 , h = 5 , w = 6 k=5,h=5,w=6k=5,h=5,w=6，从( 3 , 3 ) (3,3)(3,3)出发的走5步，第i ii行第j jj列方案数如下：
多列举一下，你会发现起点的值和其他网格的值不同，和起点同一行但不同列的网格值是一样的；和起点同一列但不同行的网格的值也是一样的，但与和起点同一行但不同列的网格值不一定一样。再看和起点不同行不同列的网格的值又是统一的另一个值。
于是我们可以对这四种情况讨论，走i ( i > = 1 ) i(i>=1)i(i>=1)步，记目标网格和起点一样的方案数为d p [ i ] [ 0 ] dp[i][0]dp[i][0],记目标网格和起点同行不同列的方案数为d p [ i ] [ 1 ] dp[i][1]dp[i][1],记目标网格和起点同列不同行的方案数为d p [ i ] [ 2 ] dp[i][2]dp[i][2],记目标网格和起点不同行不同列的方案数为d p [ i ] [ 3 ] dp[i][3]dp[i][3]。于是，我们有：
对于目的网格（下称终点）和起点一样的，可能从同行不同列(有w − 1 w-1w−1个，不包括起点所在列)或者同列不同行的网格(有h − 1 h-1h−1个，不包括起点所在行)过到来。如下图所示：
故d p [ i ] [ 0 ] = ( w − 1 ) ∗ d p [ i − 1 ] [ 1 ] + ( h − 1 ) ∗ d p [ i − 1 ] [ 2 ] ; dp[i][0]=(w-1)*dp[i-1][1]+(h-1)*dp[i-1][2];dp[i][0]=(w−1)∗dp[i−1][1]+(h−1)∗dp[i−1][2];终点是和起点同一行但不同列的网格：其上一步可能从起点、同行不同列(浅紫色格子，有w − 2 w-2w−2个)或者和起点不同行不同列的网格（灰色格子,h − 1 h-1h−1个）过到来。如下图所示：
故d p [ i ] [ 1 ] = d p [ i − 1 ] [ 0 ] + ( w − 2 ) ∗ d p [ i − 1 ] [ 1 ] + ( h − 1 ) ∗ d p [ i − 1 ] [ 3 ] ; dp[i][1]=dp[i-1][0]+(w-2)*dp[i-1][1]+(h-1)*dp[i-1][3];dp[i][1]=dp[i−1][0]+(w−2)∗dp[i−1][1]+(h−1)∗dp[i−1][3];终点是和起点同一列但不同行的网格：可能从起点、同列不同行(浅黄色格子，有h − 2 h-2h−2个)或者不同行不同列的网格(灰色格子，w − 1 w-1w−1个)过到来。如下图所示：
故d p [ i ] [ 2 ] = d p [ i − 1 ] [ 0 ] + ( h − 2 ) ∗ d p [ i − 1 ] [ 2 ] + ( w − 1 ) ∗ d p [ i − 1 ] [ 3 ] ; dp[i][2]=dp[i-1][0]+(h-2)*dp[i-1][2]+(w-1)*dp[i-1][3];dp[i][2]=dp[i−1][0]+(h−2)∗dp[i−1][2]+(w−1)∗dp[i−1][3];终点是和起点不同行不同列的网格：可能从与起点同行不同列(浅紫色带星号的格子，有1 11个)、与起点同列不同行的网格（带星号的浅黄色格子,1 11个）、或者与起点不同行不同列的网格（灰色格子，有h + w − 4 h+w-4h+w−4个）过到来。如下图所示
故d p [ i ] [ 3 ] = d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 2 ] + ( w + h − 4 ) ∗ d p [ i − 1 ] [ 3 ] dp[i][3]=dp[i-1][1]+dp[i-1][2]+(w+h-4)*dp[i-1][3]dp[i][3]=dp[i−1][1]+dp[i−1][2]+(w+h−4)∗dp[i−1][3]。
注意：结果要对998244353取模。
2.2 AC代码
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmod=998244353,maxk=1e6+5;intdp[maxk][4];signedmain(){intk,w,h,x1,x2,y1,y2;cin>>h>>w>>k;cin>>x1>>y1>>x2>>y2;dp[0][0]=1;for(inti=1;i<=k;i++){dp[i][0]=((w-1)*dp[i-1][1]%mod+(h-1)*dp[i-1][2]%mod)%mod;dp[i][1]=(dp[i-1][0]+dp[i-1][1]*(w-2)%mod+dp[i-1][3]*(h-1)%mod)%mod;dp[i][2]=(dp[i-1][0]+dp[i-1][2]*(h-2)%mod+dp[i-1][3]*(w-1)%mod)%mod;dp[i][3]=(dp[i-1][1]+dp[i-1][2]+(w+h-4)*dp[i-1][3])%mod;}if(x1==x2&&y1==y2)cout<<dp[k][0];elseif(x1==x2)cout<<dp[k][1];elseif(y1==y2)cout<<dp[k][2];elsecout<<dp[k][3];return0;}
