zcmimi's blog

arrow_back矩阵乘法共6篇文章

avatar
zcmimi
2020-09-03 21:35:00

LG 4719 【模板】"动态 DP"&动态树分治

给定一棵n个点的树,点带点权。

m次操作,每次操作给定x,y,表示修改点x的权值为y

你需要在每次操作之后

avatar
zc
2020-10-12 16:35:55

查看原题

点击跳转

矩阵加速动态规划统计有多少长度为t的路径

附加条件: 不能走过一条边以后又立刻反着走一次

如果没有附加条件,用邻接矩阵加速即可

那么如何满足这个附加条件呢?

我们设f[i][j]表示第i个时刻在第j条有向边终点的方案数,这样就可以保证不会反着走

然后构建邻接表,枚举点,更新加速矩阵信息

初始矩阵为所有与起始点直接连接的边

答案为所有与结束点连接的边的答案之和

详细可以查看代码

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

矩阵乘法

这题倍增加速比快速幂快,可以节省很多多余的计算

二进制拆位后才能矩阵运算

avatar
zc
2020-02-14 14:21:00
查看原题

点击跳转

对于第二问:

看到数据范围可以想到矩阵快速幂求斐波那契数列

矩阵乘法具有分配率: AC+BC=(A+B)C

我们可以想到用线段树维护矩阵区间乘

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题解很妙

f[i][j][k]为从ijk步的方案数

f[i][j]这个矩阵的k次方就是答案

ans = \sum f[1][i]

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们回想一下 'TJOI2017可乐'

如果边权都是1,我们可以用矩阵乘法来求邻接矩阵的k次幂

因为边权只有0-9,所以我们可以直接把一个点拆成9个

1/1
Search
search