Spy97

矩阵快速幂

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 线性基(1) 线段树(7) 莫队(1) 计算几何(30) 贪心(2)

归档

标签

去牛客网

/ 注册

全部文章 / 矩阵快速幂（共2篇）

牛客练习赛27 计数

题意： n个数字一个环，每个数字只能是3或7，要求所有相邻的m个数中，7的个数大于等于3的个数，求方案数。题解：由于m<=5，用一个数字表示最后m个数的状态，转移方程很好写： dp[i]->dp[j](j和i都合法，并且二进制下i的后m-1位和j的前m-1位相同）然后构造...

2018-09-23

0 453

2018 ICPC 徐州网络赛 K题 Morgana Net

题意：求第迭代t次后的矩阵卷积。题解：输入给出两个矩阵An，Bm 建立一个矩阵Cn*n，将矩阵A中的元素以此放到矩阵C的第一行我们将卷积的过程构造成一个转移矩阵，然后用矩阵快速幂解决构造方法：考虑点a，它周围的点a1,a2,a3,a4,a5......要参与卷积的计算中 ...

2018-09-10

0 692