线性dp-计数类题目6

题目链接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 。 t0时d[t][x1][y1]1,其他初始化为0。t0时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 ) . t1时dp[t][i][j]Σdp[t-1][x][j](1xn,x≠i)Σdp[t-1][i][y](1yw,y≠j).t1时dp[t][i][j]Σdp[t−1][x][j](1xn,xi)Σdp[t−1][i][y](1yw,yj).1.3 实现代码#includebits/stdc.husingnamespacestd;constintmod998244353;intdp[110][110][110];intmain(){intk,w,h,x1,x2,y1,y2;cinhwk;cinx1y1x2y2;dp[0][x1][y1]1;for(intt1;tk;t){for(inti1;ih;i){for(intj1;jw;j){for(intx1;xh;x)if(x!i)dp[t][i][j](dp[t][i][j]dp[t-1][x][j])%mod;for(inty1;yw;y)if(y!j)dp[t][i][j](dp[t][i][j]dp[t-1][i][y])%mod;}}}coutdp[k][x2][y2];return0;}这道题数据规模HW都到了1e9K也高达1e6暴力解法不同通过全部数据。而且多重循环会超时。2 一种AC的解法2.1 解题思路通过用暴力算法试了多个样例我发现方案数最多只会出现4个值。比如k 4 , h 3 , w 3 k4,h3,w3k4,h3,w3从( 1 , 3 ) (1,3)(1,3)出发的走4步第i ii行第j jj列方案数如下又如k 5 , h 5 , w 6 k5,h5,w6k5,h5,w6从( 3 , 3 ) (3,3)(3,3)出发的走5步第i ii行第j jj列方案数如下多列举一下你会发现起点的值和其他网格的值不同和起点同一行但不同列的网格值是一样的和起点同一列但不同行的网格的值也是一样的但与和起点同一行但不同列的网格值不一定一样。再看和起点不同行不同列的网格的值又是统一的另一个值。于是我们可以对这四种情况讨论走i ( i 1 ) i(i1)i(i1)步记目标网格和起点一样的方案数为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 hw-4hw−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](wh-4)*dp[i-1][3]dp[i][3]dp[i−1][1]dp[i−1][2](wh−4)∗dp[i−1][3]。注意结果要对998244353取模。2.2 AC代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintmod998244353,maxk1e65;intdp[maxk][4];signedmain(){intk,w,h,x1,x2,y1,y2;cinhwk;cinx1y1x2y2;dp[0][0]1;for(inti1;ik;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)%moddp[i-1][3]*(h-1)%mod)%mod;dp[i][2](dp[i-1][0]dp[i-1][2]*(h-2)%moddp[i-1][3]*(w-1)%mod)%mod;dp[i][3](dp[i-1][1]dp[i-1][2](wh-4)*dp[i-1][3])%mod;}if(x1x2y1y2)coutdp[k][0];elseif(x1x2)coutdp[k][1];elseif(y1y2)coutdp[k][2];elsecoutdp[k][3];return0;}