矩阵递推

题目

• Fibonacci 三部曲 典

  • 第n项 \(f(n)=f(n-1)+f(n-2)\)?

    \(简析\) 这是 2 阶常系数线性递推关系, 可以用矩阵来进行快速转移

    ? 令\(F(n)=\left[ {\begin{matrix}f(n-1)&f(n)\end{matrix}} \right]\)

    ? 有\(F(n)=F(n-1)·G\), 其中 \(G=\left( {\begin{matrix}0&1\\1&1 \end{matrix}} \right)\)

    ? 所以 \(F(n)=F(1)·G^{n-1}\) .　可用矩阵快速幂进行\(O(lonN)\)计算.

  • 前n项和

  • 佳佳的 即求 \(T(n)=\sum i·f(i) \bmod m\)? 　(值得一做)

    \(简析\)?

    ? 由于\(T(n)=T(n-1)+nf(n)\), 于是\(g(n)=nf(n)=g(n-1)+g(n-2)+f(n-1)+2f(n-2)\)?

    ? 定义矩阵 \(F(n)=\left( {\begin{matrix}f(n-1)&f(n)&g(n-1)&g(n)&T(n)\end{matrix}}\right)\)?

    AC代码

• 迷路 典 难 　(值得一做!)

  \(大意\)?? 给定有向图, 求 从源点出发, 恰好经过T时间 到达终点, 有多少种不同的路径.　(边权∈[0,9], N∈[2, 10], T≤10⁹ )

  \(简析\)? 先从简, 再化繁.

  1. 先考虑简单情况: 假设这个图的边权 只为 0 or 1.

     令\(f_1[i][j]: \text{结点i 恰好经过时间1 到达结点j 的方案数}\). 则题目给出的 初始01矩阵, 就是 \(f_1[i][j]\) .

     \[\]
     \[\]
     2. 但 原图中的 边权∈[0, 9]. 怎么办呢?　发现图中结点数很少, 于是我们可以 拆点

     将结点 i 拆成 9 个点. 其中第 1 个点为"真点", 其余的为"假点".

     初始化 拆点后的图: 连接 \((\ id(i,j),\ id(i,j-1)\ ) = 1\)? ?

     对于原图中的一条边 \((i, j)=x\)????. 在拆点后的图中, 连接 \((\ id(i, 0),\ id(j, x-1)\ ) = 1\)? ????? ?

     在拆点后的图进行矩阵快速幂即可.

  AC代码 int id(int i, int j){ return i*9+j; }

• GT考试 典 难 　(好难理解...)

  \(大意\) 给定一个模式串, 求母串中不出现该模式串的数量 (字符限制于 数字)

  (待补)

运算与性质

void init_1(ll o[M][M]){	// 初始化为 *单位矩阵*
	FOR(i, 0, M) FOR(j, 0, M)
		o[i][j]=(i==j ?1 :0);
}

void mmul(ll A[M][M], ll B[M][M]){			// 矩阵乘法
	ll C[M][M]; memset(C, 0, sizeof(C));	// 注意 要初始化为 0
	FOR(i, 0, M) FOR(j, 0, M) FOR(k, 0, M){
		C[i][j]=(C[i][j]+smul(A[i][k], B[k][j]))%p;	// 如果 相乘可能会爆ll, 则用龟速乘
	}
	memcpy(A, C, sizeof(C));
}

void qpow(ll C[M][M], int n){				// 矩阵快速幂
	ll res[M][M]; init_1(res);
	while(n){
		if(n&1) mmul(res, C);
		mmul(C, C); n>>=1;
	}
	memcpy(C, res, sizeof(res));
}