HDU2294--Pendant（DP，矩阵优化）

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 107 Accepted Submission(s): 69

Problem Description

On Saint Valentine's Day, Alex imagined to present a special pendant to his girl friend made by K kind of pearls. The pendant is actually a string of pearls, and its length is defined as the number of pearls in it. As is known to all, Alex is very rich, and he has N pearls of each kind. Pendant can be told apart according to permutation of its pearls. Now he wants to know how many kind of pendant can he made, with length between 1 and N. Of course, to show his wealth, every kind of pendant must be made of K pearls.
Output the answer taken modulo 1234567891.

Input

The input consists of multiple test cases. The first line contains an integer T indicating the number of test cases. Each case is on one line, consisting of two integers N and K, separated by one space.
Technical Specification
1 ≤ T ≤ 10
1 ≤ N ≤ 1,000,000,000
1 ≤ K ≤ 30

Output

            Output the answer on one line for each test case.

Sample Input

2
2 1
3 2

Sample Output

2
8

Source

The 4th Baidu Cup final

Recommend

lcy

 

想当然的以为这是一道组合数学，根本没有往动规方向想（也有组合公式，不过不会推。。。）

状态转移方程为：

以F[i][j]表示长度为i的pendant，用了j种珍珠，所构成的方案数，

则 F[i][j]=F[i-1][j]*j+F[i-1][j-1]*(k-j+1)。

可是i最大值太过巨大，所以用矩阵来优化（万能的矩阵，只要是递推就能优化。。。。）

然后注意需要求的结果是和，所以在构造矩阵时需要多加一维来计算和

矩阵如下（当然也可以有其他的构造方法）：

| 1 0...............0 1  |           |g|

| 0 1 0...............0  |           |f1|  
| 0 k-1 2.............0 |           |f2|
| .....................      |      *    .

| 0...0 k-(j-1) j 0...0|           .
| .....................     |            .
| 0...............0 1 k |            |fk|