Category Archives: 矩阵乘法

POJ 3735 Training little cats (矩阵链乘应用)

给出n个猫,然后给出k个操作,依次执行这些操作,操作:1. 给猫i加一个坚果;2.猫i将自己的坚果吃完;3. …

Codeforces 719E Sasha and Array (线段树,矩阵乘法)

给出n个数字,然后两个操作:1. l r x 将区间[l, r]的数字都加上x; 2. l r 计算区间[l, …

2016 ACM/ICPC Asia Regional Shenyang Online

1002 – List wants to travel 给出n个点的树,每条边有一种颜色,两种操作 …

FZU 2198 快来快来数一数 (矩阵乘法,优化)

f(n)表示n个蜂窝生成树的个数,求f(n)的前n项和。 不妨列出递推式: dp[i][0] = dp[i & …

Codeforces 621E. Wet Shark and Blocks (dp,矩阵乘法)

有b个块,每个块中都有相同的数字, 每个块有且选一个数字出来, 用这些数字可以组成一个新的大数, 将这个大数% …

HDU 5667 Sequence (矩阵快速幂)

计算f(n), f(n)分三种情况: 1. n = 1, f(n) = 1; 2. n = 2, f(n) = …

SGU 197 Nice Patterns Strike Back (状态压缩,矩阵快速幂)

暴力枚举两个状态,判断是否可行,写入矩阵,然后就是无脑矩阵乘法,主要是指数要用高精度存,手写一个简易版高精度类 …

HDU 5434 Peace small elephant (状态压缩,矩阵乘法)

题意:给出一个n * 7的格子,里面放一些棋子,每个旗子会攻击左上、左下、右上、右下的棋子,但是如果以下情况是 …