HDU 2294 Pendant(计数类dp+矩阵快速幂)

10-26 656 views

题意:给定k种珍珠,每种n个,求可以组成长度小于等于n并且一定包含k种珍珠的珍珠串有多少种。 思路:d[i][j] 来表示 长度为i的珍珠串中包含j种珍珠的方法数...
阅读全文 0

HDU 5318 The Goddess Of The Moon (矩阵快速幂)

9-01 534 views

题意:给定一堆序列,两个字符串可以合并当且仅当 a的后缀等于b的前缀,如果选择m个字符串(可以重复选),问可以组成多少种不同的串。 思路: 1.这个题其实...
阅读全文 0

HDU 4695 Jumping Frog (dp + m^2logn的递推优化)

8-28 1,818 views

题意: 一个青蛙上楼梯,上楼梯的时候每次走的步数给你一个限定,下楼梯的时候每次走的步数也有个限定,并且下楼梯走的台阶必须是上楼梯的台阶, 问你有多少种...
阅读全文 0

HDU 4686 Arc of Dream(矩阵快速幂)

8-27 508 views

题意:给你一个ai的递推式和 bi的递推式。求sigma(ai*bi)、 思路: 1.首先这个题目明显的是矩阵快速幂,n高达 1e18 注意要用LL, 否则会爆int、 2.关键是如...
阅读全文 0

HDU 5411 CRB and Puzzle(dp + 矩阵快速幂)

8-21 809 views

题意:直接说样例吧。n个点,k是一个长度限制,下面输入n行, 第i行先输入一个m,然后m点a,代表 i->a有一条边。 现在问你有多少种路径长度小于等于k的路...
阅读全文 0

UVA 10895- Matrix Transpose (稀疏矩阵的转置)

2-09 1,706 views

找下规律看一下就好了。 没什么难的。 就是有一个坑。 当转置之后 如果某一行元素个数为 0 的话。 要记得多输出一个空行。   ...
阅读全文 0

10655 – Contemplation! Algebra (矩阵快速幂)

1-25 579 views

这个题自己一开始做的时候。一看  a+b  ab  想到了一元二次方程。 但是一元二次方程 会有虚根。 然后再快速幂 求 n次方。。 但是如果有根号的话 就会有精度损...
阅读全文 0

UVA 1386 Cellular Automaton(循环矩阵乘法快速幂)

1-05 735 views

循环矩阵第一次听说。 当然写起来感觉还好。 有一个重要的性质。 循环矩阵的 n 次 幂  仍然是循环矩阵。 这个很重要。 直接用 O(n^3)的算法太慢。 那么我们...
阅读全文 0
加载更多