HDU 2294 Pendant

HDU_2294

    我们可以用f[i][j]表示珠子长度为i的时候一共有j种颜色的方案数，那么就有f[i][j]=j*f[i-1][j]+(K-j+1)*f[i-1][j-1]，最后的结果就是f[1][K]+f[2][K]+…+f[N][K]。

    但由于N比较大，我们不能直接计算，但有了递推方程以后发现是可以构造出K*K的矩阵后用二分矩阵的方法去快速计算f[i][K]的，但对于f[1][K]+f[2][K]+…+f[N][K]这个表达式该如何求解呢？

    如果我们将构造出的递推关系的矩阵看成矩阵A，然后就可以用POJ_3233的方法先求A+A^2+A^3+…+A^K，然后就比较容易得到结果了。

    或者我们可以用g[i][j]表示珠子长度不超过i时一共有j种颜色的方案数，那么g[i][j]=g[i-1][j]+f[i][j]，而最后结果就是g[N][K]，这样我们也可以利用f[i][j]=j*f[i-1][j]+(K-j+1)*f[i-1][j-1]和g[i-1][j]=g[i-2][j]+f[i-1][j]这两个递推关系构造一个2K*2K的矩阵，然后二分这个矩阵直接求解，我的代码就是用这种方式写的。

#include<stdio.h>
#include<string.h>
#define MAXD 61
#define D 1234567891
int N, K, cnt;
struct Matrix
{
    long long a[MAXD][MAXD];
    void init()
    {
        int i;
        memset(a, 0, sizeof(a));
        for(i = 1; i < K; i ++)
            a[i][i] = K - i + 1, a[i][i + 1] = i;
        a[K][K] = 1;
        for(i = 1; i <= K; i ++)
            a[i + K][i + K] = 1, a[i + K][i] = 1;
    }
}mat[150];
int multiply(int x, int y)
{
    int i, j, k, z = ++ cnt;
    long long ans;
    for(i = 1; i <= (K << 1); i ++)
        for(j = 1; j <= (K << 1); j ++)
        {
            ans = 0;
            for(k = 1; k <= (K << 1); k ++)
                ans = (ans + mat[x].a[i][k] * mat[y].a[k][j]) % D;
            mat[z].a[i][j] = ans;
        }
    return z;
}
int powmod(int n)
{
    int k;
    if(n == 1)
        return 0;
    k = powmod(n >> 1);
    k = multiply(k, k);
    if(n & 1)
        k = multiply(k, 0);
    return k;
}
void solve()
{
    int k;
    scanf("%d%d", &N, &K);
    mat[0].init();
    cnt = 0;
    k = powmod(N - 1);
    printf("%I64d\n", (mat[k].a[1][K] * K + mat[k].a[K + 1][K] * K) % D);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        if(N == 1)
            printf("%d\n", K == 1 ? 1 : 0);
        else
            solve();
    }
    return 0;
}