pendant.cpp

第四届百度杯编程大赛final解题报告+标程

/**********************************************************************
Author: Sherlock
Created Time:  2009-03-24 19:51:46
File Name: necklace.cpp
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

#define int64 long long

const   int     mod =   1234567891;

int     n, m;
int     a[31][31], b[31][31], c[31][31], d[31][31], z[31][31];

void        mul(int x[31][31], int y[31][31])
{
    for (int i = 0; i <= m; i ++)
        for (int j = 0; j <= m; j ++)
        {
            z[i][j] = 0;
            for (int k = 0; k <= m; k ++)
                z[i][j] = ((int64) z[i][j] + ((int64) x[i][k] * y[k][j]) % mod) % mod;
        }
    for (int i = 0; i <= m; i ++)
        for (int j = 0; j <= m; j ++)
            x[i][j] = z[i][j];
}

void        make(int p)
{
    if (p == 0)
        return ;
    make(p / 2);
    for (int i = 0; i <= m; i ++)
        for (int j = 0; j <= m; j ++)
            d[i][j] = b[i][j];
    for (int i = 0; i <= m; i ++)
        d[i][i] = (d[i][i] + 1) % mod;
    mul(c, d);
    mul(b, b);
    if (p % 2 == 1)
    {
        mul(b, a);
        for (int i = 0; i <= m; i ++)
            for (int j = 0; j <= m; j ++)
                c[i][j] = ((int64) c[i][j] + b[i][j]) % mod;
    }
}

void        solve()        
{ 
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for (int i = 0; i <= m; i ++)
        b[i][i] = 1;
    for (int i = 1; i <= m; i ++)
    {
        a[i - 1][i] = m - i + 1;
        a[i][i] = i;
    }
    make(n);
    printf("%d\n", c[0][m]);
} 

int         main()
{
    int test_num;
    scanf("%d", &test_num);
    while (test_num > 0)
    {
        test_num --;
        scanf("%d%d", &n, &m);
        solve();
    }
}