题意:给定k种珍珠,每种n个,求可以组成长度小于等于n并且一定包含k种珍珠的珍珠串有多少种。

思路:d[i][j] 来表示 长度为i的珍珠串中包含j种珍珠的方法数,

如果j==1,d[i][j] = d[i – 1][j]。

其他的,d[i][j] += d[i – 1][j – 1] * (k – j + 1)代表在每个串后面都可以添加k-j+1种新的珍珠。

d[i][j] += d[i – 1][j]*j 代表可以在每个串后面添加一个已经存在过的珍珠。

我们发现在递推的过程中,后面的常数只和j有关,那么我们可以构造矩阵.

让A矩阵为 [d[1][0], d[1][1],d[1][2]…,sum]。

转移的时候的B矩阵根据上面的状态转移推一下即可,然后矩阵快速幂。得出的sum即为最后结果,

 

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

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

阅读全文

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

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

阅读全文

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

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

阅读全文

欢迎留言

*