首页 > ACM题库 > HDU-杭电 > HDU 3509-Buge’s Fibonacci Number Problem[解题报告]HOJ
2014
04-09

HDU 3509-Buge’s Fibonacci Number Problem[解题报告]HOJ

Buge’s Fibonacci Number Problem

问题描述 :

snowingsea is having Buge’s discrete mathematics lesson, Buge is now talking about the Fibonacci Number. As a bright student, snowingsea, of course, takes it as a piece of cake. He feels boring and soon comes over drowsy.
Buge,feels unhappy about him, he knocked at snowingsea’s head, says:”Go to solve the problem on the blackboard!”, snowingsea suddenly wakes up, sees the blackboard written :

Product of coprimes

snowingsea thinks a moment,and writes down:

Product of coprimes

snowingsea has a glance at Buge,Buge smiles without talking, he just makes a little modification on the original problem, then it becomes :

Product of coprimes

The modified problem makes snowingsea nervous, and he doesn’t know how to solve it. By the way,Buge is famous for failing students, if snowingsea cannot solve it properly, Buge is very likely to fail snowingsea. But snowingsea has many ACM friends. So,snowingsea is asking the brilliant ACMers for help. Can you help him?

输入:

The input consists of several test cases. The first line contains an integer T representing the number of test cases. Each test case contains 7 integers, they are f1, f2, a, b, k, n, m which were just mentioned above, where 0 < f1, f2, a, b, n, m < 1000 000 000, and 0 ≤ k < 50.

输出:

The input consists of several test cases. The first line contains an integer T representing the number of test cases. Each test case contains 7 integers, they are f1, f2, a, b, k, n, m which were just mentioned above, where 0 < f1, f2, a, b, n, m < 1000 000 000, and 0 ≤ k < 50.

样例输入:

3
1 1 1 1 1 2 100000
1 1 1 1 1 3 100000
1 1 1 1 1 4 100000

样例输出:

2
4
7

http://acm.hdu.edu.cn/showproblem.php?pid=3509

调试了一个晚上终于AC了,态蛋疼了,全都是非常脑残的错误……

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

ll a[52][52],b[52][52],c[52][52],mod,zu[52][52];
ll s[52];

void cal(ll a1[][52],ll b1[][52],ll c1[][52],int size)
{
    for(int i=0;i<size;i++)
    for(int j=0,r;j<size;j++)
    for(r=0,c1[i][j]=0;r<size;r++)
      c1[i][j]=(c1[i][j]+a1[i][r]*b1[r][j])%mod;
}
ll quick_cal(int n,int size)
{
    while(n)
    {
        if(n&1)
        {
            cal(a,c,b,size);
            memcpy(c,b,sizeof(b));
        }
        n>>=1;
        cal(a,a,b,size);
        memcpy(a,b,sizeof(b));
    }
    ll ans=0;
    for(int i=0;i<size;i++)
      ans=(ans+c[0][i]*s[i])%mod;
    return ans;
}
ll tmpa[52],tmpb[52];

int main()
{
    int x;
    zu[0][0]=1;
    zu[1][0]=zu[1][1]=1;
    for(int i=2;i<=50;i++)
    {
        zu[i][0]=zu[i][i]=1;
        for(int j=1;j<i;j++)
         zu[i][j]=zu[i-1][j-1]+zu[i-1][j];
    }
    ll f1,f2,a1,b1,n;
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%I64d %I64d %I64d %I64d %d %I64d %I64d",&f1,&f2,&a1,&b1,&x,&n,&mod);
        s[0]=1;
        for(int i=0;i<x;i++) s[0]=s[0]*f1%mod;
        if(n==1)
        {
            printf("%I64d\n",s[0]);
            continue;
        }
        ll tmp=1;
        for(int i=0;i<x;i++) tmp=tmp*f2%mod;
        s[0]=(s[0]+tmp)%mod;
        if(n==2)
        {
            printf("%I64d\n",s[0]);
            continue;
        }
        tmp=1;
        for(int i=0;i<x;i++) tmp=tmp*(a1*f2+b1*f1)%mod;
        s[0]=(s[0]+tmp)%mod;
        if(n==3)
        {
            printf("%I64d\n",s[0]);
            continue;
        }
        tmp=1;
        int k=x;
        //cout<<a1<<" "<<f2<<" "<<b1<<" "<<f1<<endl;
        for(int i=1;i<k+2;i++)
        {
            ll tmp1=1;
            for(int j=0;j<k-i+1;j++) tmp1=tmp1*f2%mod;
            s[i]=tmp1*tmp;
            tmp=tmp*(a1*f2+b1*f1)%mod;
        }
        tmpa[0]=tmpb[0]=1;
        for(int i=1;i<=x;i++)
          tmpa[i]=tmpa[i-1]*a1%mod;
        for(int i=1;i<=x;i++)
          tmpb[i]=tmpb[i-1]*b1%mod;
        //cout<<tmpb[1]<<endl;
        memset(a,0,sizeof(a));
        a[0][0]=1;
        for(int i=1;i<x+2;i++)
          a[0][i]=tmpa[i-1]*tmpb[x-i+1]%mod*zu[x][i-1]%mod;
        //cout<<tmpb[0]<<" dsdf "<<tmpb[2]<<endl;

        for(int i=1;i<x+2;i++)
        {
            for(int j=0;j<i;j++)
             a[i][k+1-j]=tmpb[j]*tmpa[i-1-j]%mod*zu[i-1][i-1-j]%mod;
        }
        memset(c,0,sizeof(c));
        for(int i=0;i<x+2;i++)
           c[i][i]=1;
        printf("%I64d\n",quick_cal(n-3,x+2));
    }
    return 0;
}
// 1 2 1 2 1 5 100000

参考:http://blog.csdn.net/struggle_mind/article/details/7797658