题解：CF2204G Grid Path
MaxBlazeResFire
·
·
题解
你们矩阵边长怎么都是 2m 的，不卡常吗？
显然每一行占据一个区间。一个合法的 pattern 可以用唯一的一个区间集合 [l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k] 描述，要求相邻有交，且 l_1=1。
我们的目标显然是矩阵快速幂优化，考察有 l_1=1 的限制不好做，于是从下到上倒着对这个 pattern 做 dp，f_{i,l,r} 表示第 [i,n] 行，其中第 i 行占据 [l,r] 的方案数。
转移方程
我们的目标显然是矩阵快速幂优化，所以状态数太多必须考虑某种缩减，记 $s_i$ 表示 $\sum_{1\leq l\leq r\leq i}f_{l,r}$，$t_i$ 表示 $\sum_{i\leq l\leq r\leq m}f_{l,r}$，则有
$\displaystyle f_{i,l,r}=1+s_m-s_{l-1}-t_{r+1}$。
不难想到直接对 $s,t$ 做转移，直接裸拆贡献有 $s'_i=\frac{i(i+1)}{2}(s_m+1)-\sum_{l\leq i}(i-l)s_l-\sum_{r\leq i+1}(r-1)t_r$。
显然可以把 $s,t$ 并排放置用矩阵优化。但是矩阵太大不好，考虑对称性，有 $t_i=s_{m-i+1}$，于是矩阵大小减半。
最后答案显然就是 $s_m-s_{m-1}$。
$O(m^3\log n)$，不带 $8$ 的常数，轻松跑。
感谢 @Snakes。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 155
int n,m,mod;
inline void chkadd( int &x , int k ){ x += k; if( x >= mod ) x -= mod; }
struct matrix{
int a[MAXN][MAXN];
matrix(){ memset( a , 0 , sizeof( a ) ); }
inline int* operator []( int x ){ return a[x]; }
inline void build(){
for( int i = 0 ; i < MAXN ; i ++ )
for( int j = 0 ; j < MAXN ; j ++ ) a[i][j] = i == j;
}
inline matrix operator *( matrix B ){
matrix C;
for( int k = 0 ; k < MAXN ; k ++ )
for( int i = 0 ; i < MAXN ; i ++ )
for( int j = 0 ; j < MAXN ; j ++ )
chkadd( C[i][j] , a[i][k] * B[k][j] % mod );
return C;
}
}R;
inline matrix fp( matrix A , int p ){
matrix res; res.build();
while( p ){
if( p & 1 ) res = res * A;
A = A * A;
p >>= 1;
}
return res;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&mod);
if( m == 1 ){ printf("%lld\n",n % mod); return 0; }
//来裸配系数
R[0][0] = 1;
for( int i = 1 ; i <= m ; i ++ ){
chkadd( R[m][i] , i * ( i + 1 ) / 2 % mod );
chkadd( R[0][i] , i * ( i + 1 ) / 2 % mod );
for( int j = 1 ; j <= i ; j ++ )
chkadd( R[j][i] , ( mod - ( i - j + mod ) % mod ) % mod );
for( int j = 2 ; j <= min( i + 1 , m ) ; j ++ )
chkadd( R[m - j + 1][i] , ( mod * mod - ( j - 1 ) ) % mod );
}
//初值？
matrix st; st[0][0] = 1;
for( int i = 1 ; i <= m ; i ++ ) st[0][i] = i * ( i + 1 ) / 2 % mod;
st = st * fp( R , n - 1 );
printf("%lld\n",( st[0][m] - st[0][m - 1] + mod ) % mod);
return 0;
}
```