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]=A^i-1*F[1]，所以F[1]+…+F[n]=A⁰*F[1]+…+A^n-1*F[1]=（E+A+A²+…+A^n-1)*F[1]。

F[i-1]这个矩阵是

F[i-1][0]<wbr></wbr>F[i-1][1]<wbr></wbr>F[i-1][2] ......<wbr></wbr>F[i-1][k]

0<wbr></wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>0<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>0<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>……<wbr></wbr>0<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>

.<wbr><wbr></wbr></wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>.

.<wbr><wbr></wbr></wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>.<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>.

0<wbr></wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>0<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>0<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>0<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>0

(这是个K+1阶的阶阵)

<wbr></wbr>

<wbr></wbr>A矩阵是

0<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>k<wbr></wbr>0<wbr></wbr><wbr><wbr></wbr></wbr>0<wbr></wbr>0<wbr></wbr>0

0<wbr></wbr>1<wbr></wbr>k-1<wbr></wbr>0<wbr></wbr>0<wbr></wbr>0

0<wbr></wbr>0<wbr></wbr>2<wbr><wbr><wbr></wbr></wbr></wbr>0<wbr></wbr>0<wbr></wbr>0

.<wbr><wbr></wbr></wbr>.<wbr></wbr>.<wbr><wbr><wbr></wbr></wbr></wbr>.<wbr><wbr></wbr></wbr>.<wbr><wbr></wbr></wbr>.

.<wbr><wbr></wbr></wbr>.<wbr></wbr>.<wbr><wbr><wbr></wbr></wbr></wbr>.<wbr><wbr></wbr></wbr>.<wbr><wbr></wbr></wbr>.

0<wbr></wbr>0<wbr></wbr>0<wbr><wbr></wbr></wbr>0<wbr><wbr></wbr></wbr>k-1<wbr></wbr>1

0<wbr></wbr>0<wbr></wbr>0<wbr><wbr></wbr></wbr>0<wbr><wbr></wbr></wbr>0<wbr><wbr></wbr></wbr>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\n",series.matrix[0][2*n-1]);
    }
    return 0;
}