hdu 2294 pendant

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2294
F [i] [j] 로 길 이 를 i 로 표시 하 는 pendant 는 j 종의 진 주 를 사 용 했 고 구 성 된 방안 수 는 F [i] [j] = F [i - 1] [j] * j + F [i - 1] [j - 1] * (k - j + 1) 이다.결 과 는 F [1] [k] +... + F [n] [k] 입 니 다.
행렬 로 하 다.F [i - 1] 에서 F [i] 로 의 전 이 를 행렬 로 묘사 하면 k * k 의 선형 변환 행렬 에 해당 합 니 다.따라서 F [i] = A * F [i - 1], 여기 A 는 전이 행렬, 즉 F [i] = Ai - 1 * F [1], 그래서 F [1] +... + F [n] = A0 * F [1] +... + An - 1 * F [1] = (E + A + A2 +... + An - 1) * F [1].
 F [i - 1] 이 행렬 은...
F[i-1][0]  F[i-1][1]  F[i-1][2] ......  F[i-1][k]
0        0        0      ……  0     
.         .        .       .     .
.         .        .       .     .
0        0        0      0     0
(이것 은 K + 1 단계 의 단계 진 입 니 다)
 
  A 행렬 은
0          k  0    0  0  0
0  1  k-1  0  0  0
0  0  2    0  0  0
.   .  .    .   .   .
.   .  .    .   .   .
0  0  0   0   k-1  1
0  0  0   0   0   k. 그 다음은 행렬 멱 의 템 플 릿 입 니 다.
제목 원본:

#include <iostream>
using namespace std;

struct node
{
    long long matrix[31][62];
};

node series;
int n, m;


node multiply(node a,node b)
{
    node res;
    int i,j,k;
    memset(res.matrix,0,sizeof(res.matrix));
    for (i=0;i<n;++i)
        for (j=0;j<n;++j)
        {
            for (k=0;k<n;++k)       //                    
                res.matrix[i][j]=(res.matrix[i][j] + a.matrix[i][k] * b.matrix[k][j])%m;
        }
    for (i=0;i<n;++i)
        for (j=n;j<2*n;++j)
        {
            res.matrix[i][j]=a.matrix[i][j]%m;
            for (k=0;k<n;++k)       //         ,  wa
                res.matrix[i][j]=(res.matrix[i][j] + a.matrix[i][k] * b.matrix[k][j])%m;
        }
    return res;
}
node pow(node mtx,int k)
{
    if (k==1)
        return mtx;
    else if (k%2)
        return multiply( pow(multiply(mtx,mtx),k/2) , mtx );
    else
        return pow(multiply(mtx,mtx),k/2);
}

void solve(int k)//   n      
{
    int i,j;
    for (i=1;i<n;++i)
    {
        //                
        series.matrix[i][i]=i;
        series.matrix[i-1][i]=n-i;
    }
    for (i=0,j=n;i<n;++i,++j)
    {
        //  i==j         1,   0,       1     
        series.matrix[i][j]=1;
    }
    series=pow(series,k+1);
    for (i=0,j=n;i<n;++i,++j)
    {
        series.matrix[i][j]--;
    }
}

int main()
{
    int k,t;
    scanf("%d",&t);
    while (t--)
    {
        memset(series.matrix,0,sizeof(series.matrix));
        scanf("%d%d",&k,&n);//n      k    
        n++;
        m=1234567891;
        solve(k);
        printf("%d
",series.matrix[0][2*n-1]);
    }
    return 0;
}