HDU 2294 Pendant

/*
*  [题意]
*   有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>
#include <ctime>
using namespace std;
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)
#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};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    LL tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + (LL)b[i][j]*a[j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    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++)
        {
            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);
        matmul(ans, ret, k+1);
        cout << ans[0] << endl;
    }
    return 0;
}