Pendant
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 636 Accepted Submission(s): 322
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.
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
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
/*
HDU 2294 DP+矩阵快速幂
开始题意都没看懂，看别人的。
有k种珍珠，每种珍珠N个，问长度<=N且有k种珍珠的垂饰有多少个？
dp[i][j]表示长度为i的并且有j种珍珠的垂饰有多少个
则有状态转移：dp[i][j] = (k-(j-1))*dp[i-1][j-1] + j*dp[i-1][j];
由于N太大，所以把i看成“阶段”，构造矩阵，通过矩阵快速转移
设第i阶段的一维数组(dp[i][0~j])状态设为F，转移矩阵为init（k+1阶方阵）
则有：init * F = F';（F'为新状态）
设答案 = gn = dp[1][k] + dp[2][k] + ... + dp[n][k]
所以有矩阵：
| 1 0...............0 1 | |g0| |g1'|
| 0 1 0...............0 | |f1| |f1'|
| 0 k-1 2.............0 | |f2| |f2'|
| ..................... | * |..| = |..'|
| 0...0 k-(j-1) j 0...0 | |fj| |fj'|
| ..................... | |..| |..'|
| 0...............0 1 k | |fk| |fk'|
这个代码的初始化：[g0, f1, f2, ..., fk] = {0, k, 0, ..., 0}
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define LL long long
#define M 35
int ans[M], mod = 1234567891;
int ret[M][M];
int init[M][M];
void matmul(int a[][M], int b[][M], int n)
{
LL tp[M][M] = {0};
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)
if(a[i][k])
for(int j=0;j<n;j++)
if(b[k][j])
tp[i][j]=(tp[i][j]+(LL)a[i][k]*b[k][j])%mod;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j] = tp[i][j];
}
void lastMul(int a[], int b[][M], int n)
{
LL tp[M] = {0};
for(int j=0;j<n;j++)
if(a[j])
for(int i=0;i<n;i++)
if(b[i][j])
tp[i] = (tp[i] + (LL)b[i][j]*a[j]) % mod;
for(int i=0;i<n;i++)
a[i]=tp[i];
}
void qmod(int n, int b)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ret[i][j]=(i==j);//初始化 k+1阶单元阵
for (;b;b>>= 1)
{
if (b&1)
matmul(ret,init,n);
matmul(init,init,n);
}
}
int main()
{
int t, n, k, i, j;
cin>>t;
while(t--)
{
cin>>n>>k;
memset(init,0,sizeof(init));
init[0][0]=init[0][k]=1;
for(j=1;j<=k;j++)//初始化init矩阵
{
if(j>1)
init[j][j-1]=k-(j-1);
init[j][j]=j;
}
memset(ans,0,sizeof(ans));
ans[1]=k;
qmod(k+1,n);//计算A
lastMul(ans,ret,k+1);
cout<<ans[0]<<endl;
}
return 0;
}