【矩阵乘法】JZOJ_4787 数格子

本文主要是介绍【矩阵乘法】JZOJ_4787 数格子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

求出用$2\times 1$的牌填满$4\times N$的矩形方案数%$M$。

思路

可以打表，得出$1,5,11,36,95$，之后代入$OEIS$，得出递推公式（逃
$$a(n)=a(n-1)+5\ast a(n-2)+a(n-3)-a(n-4)$$
矩阵乘法加速递推即可。

代码

#include<cstdio>
#include<cstring>int n, m;
struct matrix{int a[5][5];
};matrix operator *(matrix &a, matrix &b){matrix c;memset(c.a, 0, sizeof(c.a));for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)for (int k = 1; k <= 4; k++)c.a[i][j] = (c.a[i][j] + (long long)a.a[i][k] * b.a[k][j]) % m;return c;
}void power(int b) {matrix A;memset(A.a, 0, sizeof(A.a));A.a[1][4] = -1;A.a[2][1] = 1;A.a[2][4] = 1;A.a[3][2] = 1;A.a[3][4] = 5;A.a[4][3] = 1;A.a[4][4] = 1;matrix r;r.a[1][1] = 1;r.a[1][2] = 5;r.a[1][3] = 11;r.a[1][4] = 36;for (; b; b >>= 1) {if (b & 1) r = r * A;A = A * A;}printf("%d\n", r.a[1][4]);
}int main() {while (scanf("%d %d", &n, &m), n || m) {if (n == 1) printf("1\n");else if (n == 2) printf("5\n");else if (n == 3) printf("11\n");else if (n == 4) printf("36\n");else if (n == 5) printf("95\n");else power(n - 4);}
}

这篇关于【矩阵乘法】JZOJ_4787 数格子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---