hdu 3509 Buge's Fibonacci Number Problem

点击此处即可传送 hdu 3509

题目大意：F1 = f1, F2 = f2;;
F(n) = a*F(n-1) + b*F(n-2);
S(n) = F1^k + F2^k +….+Fn^k;
求S(n) mod m;
解题思路：
1:首先一个难题就是怎么判断矩阵的维数（矩阵的维数是个变量）
解决方法：开一个比较大的数组，然后再用一个公有变量记一下就行了，具体详见代码；
2：k次方，找规律；
具体上代码吧：

/*
2015 - 8 - 16 晚上
Author: ITAK

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 54;
LL mod, size;//size = 矩阵大小
typedef struct
{
    LL m[maxn][maxn];
} Matrix;

Matrix P;
Matrix I;
//正常快速幂
LL quick_mod(LL a, LL b, LL c)
{
    LL ans = 1;
    if(b == 0)
        return 1;
    while(b)
    {
        if(b & 1)
            ans = (ans*a)%c;
        b >>= 1;
        a = (a*a)%c;
    }
    return ans;
}
//矩阵乘法
Matrix matrix_mul(Matrix a, Matrix b)
{
    int i, j, k;
    Matrix c;
    for(i=0; i<size; i++)
    {
        for(j=0; j<size; j++)
        {
            c.m[i][j] = 0;
            for(k=0; k<size; k++)
            {
                c.m[i][j] += ((a.m[i][k]%mod)*(b.m[k][j]%mod))%mod;
            }
            c.m[i][j] %= mod;
        }
    }
    return c;
}
//矩阵的快速幂
Matrix quick_pow(LL m)
{
    Matrix b=P, ans=I;
    while(m)
    {
        if(m & 1)
            ans = matrix_mul(ans, b);
        m >>= 1;
        b = matrix_mul(b, b);
    }
    return ans;
}
//组合数。。。
LL c[50][50];
int main()
{
    memset(c, 0, sizeof(c));
    for(int i=0; i<50; i++)
    {
        c[i][0] = 1;
        c[i][i] = 1;
    }
    for(int i=1; i<50; i++)
        for(int j=1; j<i; j++)
            c[i][j] = c[i-1][j] + c[i-1][j-1];
    int t;
    Matrix tmp;
    LL f1, f2, a, b, k, n, m ;
    LL sum, ans1, ans2;
    //scanf("%d",&t);
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin>>f1>>f2>>a>>b>>k>>n>>mod;
        //scanf("%lld%lld%lld%lld%lld%lld%lld",&f1,&f2,&a,&b,&k,&n,&mod);
        memset(P.m, 0, sizeof(P.m));
        memset(I.m, 0, sizeof(I.m));
        if(k == 0)
            printf("%lld\n",n%mod);
        else
        {
            if(n == 1)
                cout<<quick_mod(f1, k, mod)<<endl;
            else if(n == 2)
                cout<<(quick_mod(f1,k,mod) + quick_mod(f2,k,mod))%mod<<endl;
            else
            {
                size = k+2;
                //矩阵赋值
                for(int i=0; i<size; i++)
                    I.m[i][i] = 1;
                P.m[0][0] = 1;
                P.m[0][size-1] = 1;
                for(int i=1; i<size-1; i++)
                    P.m[0][i] = 0;
                for(int i=1; i<size; i++)
                    for(int j=size-i,w=0; j<size; j++,w++)
                    {
                        P.m[i][j]=(((c[i-1][w]%mod)*quick_mod(a,w,mod))%mod)*quick_mod(b,i-1-w,mod);
                        P.m[i][j] %= mod;
                    }
                tmp = quick_pow(n-1);
                sum = (sum+(tmp.m[0][0]%mod)*(quick_mod(f1,k,mod)))%mod;
                for(int i=1; i<size; i++)
                {
                    ans1 = (quick_mod(f1,size-1-i,mod)*quick_mod(f2,i-1,mod))%mod;
                    ans2 = (ans1*(tmp.m[0][i]%mod))%mod;
                    sum = (sum+ans2)%mod;
                }
                cout<<sum%mod<<endl;
            }
        }
    }
    return 0;
}