The solution of「CF2204G Grid Path」
\textup{CF2204G Grid Path}
基础的矩阵快速幂可以看这个。
:::info[笑点] :::
\textup{\textup{Description}}
在
问路径上格子的集合的种数。
\textup{\textup{Solution}}
详细推一波转移矩阵，比较长就折起来了。
:::success[矩阵转移] 为了方便，我们令
g_i = g_{i - 1} \times A 。小心我的系数变量和前面不统一。
在
1 \to m 列中，计算pre_{i, y} 根据上面的公式（可以对着前面看），分别在矩阵A 中填写这三项。
- 系数为
\frac{y \cdot (y - 1)}{2} ，即A_{2m + 1, y} ；- 系数为
-(y - l) ，令x = l ，则在x < y 时，A_{x, y} = -( y - x ) ；- 系数为
-r ，令x = r ，在x < y 的时候，A_{m + x, y} = -x 。+ 系数为 $\frac{(m - y)(m - y + 1)}{2}$，即 $A_{2m + 1, m + y}$； + 系数为 $-(m - l + 1)$，在 $x > y$ 时，$A_{x, m + y} = -(m - x + 1)$； + 系数为 $-(r - y)$，在 $x > y$ 时，$A_{m + x, m + y} = -(x - y)$。 $tot_i$ 也同理。 + 系数为 $\frac{m \cdot (m + 1)}{2}$，即 $A_{2m + 1, 2m + 1} = \frac{m \cdot (m + 1)}{2}$； + 系数为 $-(m + 1 - l)$，对所有 $1 \le x \le m$，$A_{x, 2m + 1} = -(m + 1 - x)$； + 系数为 $-r$，对所有 $1 \le x \le m$，$A_{m + x, 2m + 1} = -x$。 回收 $sum_i$ 的伏笔，由于其定义是前 $i$ 行的方案数前缀和，也就是 $sum_i = sum_{i - 1} + pre_{i, m + 1}$，在矩阵中的系数就呼之欲出了。 又因为 $pre_{i, m + 1} = g_{i - 1, 1} \cdot A_{1, 2m + 1} + \cdots + g_{i - 1, 2m + 1} \cdot A_{2m + 1, 2m + 1}$，所以系数相同。 那么有对于 $x \le 2m + 1$，$A_{x, 2m + 2} = A_{x, 2m + 1}$，以及最后从上一行继承的 $sum$，即 $A_{2m + 2, 2m + 2} = 1$。 于是我们转移完了。 ::: 这样就可以做到 $O( ( 2m ) ^ 3 \cdot n)$ 了，常数稍微卡卡就能过，反正也是对的。
\textup{\textup{Code}}
回收开头笑点的伏笔，似乎会卡常，所以开 int128 然后最后统一取模会快很多，快速幂也可以像我代码这样写会快一点。
#include<bits/stdc++.h>
#define lll __int128
#define ll long long
using namespace std;
const int MAXN = 310;
int N, M, MOD, siz;
lll tmp[MAXN][MAXN];
// #define int long long
struct matrix{
int a[MAXN][MAXN];//转移矩阵A
void unit(){
for( int i = 1; i <= siz; i ++ )
for( int j = 1; j <= siz; j ++ )
a[i][j] = ( i == j );
}
matrix operator * ( const matrix & b ) const{
memset( tmp, 0, sizeof tmp );
matrix ans;
for( int i = 1; i <= siz; i ++ )
for( int k = 1; k <= siz; k ++ ){
if( !a[i][k] ) continue;
for( int j = 1; j <= siz; j ++ )
tmp[i][j] += 1ll * a[i][k] * b.a[k][j];
// ans.a[i][j] = 0;
// ans.a[i][j] = ( a[i][k] * b.a[k][j] % MOD + ans.a[i][j] % MOD ) % MOD;
}
for( int i = 1; i <= siz; i ++ )
for( int j = 1; j <= siz; j ++ )
ans.a[i][j] = tmp[i][j] % MOD;
return ans;
}
}a, g;
matrix qpow( matrix a, int x ){
matrix ans;
// base = *this;
ans.unit();
while( x ){
if( x & 1ll ) ans = ans * a;
a = a * a;
x >>= 1;
}
return ans;
}
signed main(){
cin >> N >> M >> MOD;
siz = M * 2 + 2;
for( int y = 1; y <= M; y ++ ){//pre
a.a[2 * M + 1][y] = ( 1ll * y * ( y - 1 ) / 2 + MOD) % MOD;
for( int l = 1; l < y; l ++ )
a.a[l][y] = ( - y + l + MOD ) % MOD;
for( int r = 1; r < y; r ++ )
a.a[M + r][y] = ( -r + MOD ) % MOD;
}
for( int y = 1; y <= M; y ++ ){//suf
a.a[2 * M + 1][y + M] = ( 1ll * ( M - y ) * ( M - y + 1 ) / 2 + MOD) % MOD;
for( int l = y + 1; l <= M; l ++ )
a.a[l][y + M] = ( -( M - l + 1 ) + MOD ) % MOD;
for( int r = y + 1; r <= M; r ++ )
a.a[M + r][y + M] = ( -( r - y ) + MOD ) % MOD;
}
int ytot = 2 * M + 1;//tot
a.a[ytot][ytot] = ( 1ll * M * ( M + 1 ) / 2 ) % MOD;
for( int l = 1; l <= M; l ++ )
a.a[l][ytot] = ( -( M + 1 - l ) + MOD ) % MOD;
for( int r = 1; r <= M; r ++ )
a.a[M + r][ytot] = ( -r + MOD ) % MOD;
int ysum = 2 * M + 2;//sum
for( int x = 1; x <= 2 * M + 1; x ++ )
a.a[x][ysum] = a.a[x][ytot];
a.a[2 * M + 2][ysum] = 1;
g.a[1][2 * M + 1] = g.a[1][2 * M + 2] = M % MOD;//tot和sum初始都是M
for( int i = 1; i <= M; i ++ )
g.a[1][i] = ( i - 1 ) % MOD;//pre
a = qpow( a, N - 1 );
g = g * a;
cout << g.a[1][siz];
return 0;
}\textup{Last}
敲柿子快敲死了，怕错所以用了 ai 复核了点下标可能写的有点 ai 味（比如那个大括号），见谅。
审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。
如果您觉得本文写的还不错，那可以留个赞吗？
谢谢你看到这里~