zzuli 1605 数字序列 （矩阵快速幂取模）

题目描述

一个数列的定义如下：

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A和B，你要求出f(n).

输入

输入包含多个测试案例。每个测试用例包含3个整数A，B和n在一行（1＜＝A，B≤1000，1≤n≤100000000）。

当输入三个0表示结束

输出

对于每个测试案例，输出f(n)，单独占一行。

样例输入 

1 1 3
1 2 10
0 0 0

样例输出 

2
5

分析：斐波那契数列的变种题目，很容易可以推出系数矩阵

那么这个矩阵的n-3次方乘以初始矩阵A0(A0[1][1]=f(2)，A0[2][1]=f(1)，其余均为0)，得到的矩阵C的第1行第1列的数字就是答案。

注意：矩阵乘法不满***换律！

代码：

#include<stdio.h>
const long long int maxn=20,mod=7;
struct matrix
{
    long long int s[maxn][maxn];

};
long long int a,b;
matrix res,ans;
matrix mul(matrix A,matrix B,long long int n)
{
    matrix C;
    for(long long int i = 1 ; i<=n ; i++)
        for(long long int j= 1 ; j<=n ; j++)
            C.s[i][j]=0;

    for(long long int i= 1 ; i<=n ; i++)
        for(long long int j=1 ; j<= n ; j++)
            for(long long int k = 1 ; k<= n; k++)
                C.s[i][j]+=A.s[i][k]*B.s[k][j];

    return C;
}
void quick(long long int y,long long int n)
{



    ans.s[1][1]=a;
    ans.s[1][2]=b;
    ans.s[2][1]=1;
    ans.s[2][2]=0;

    res=ans;
    while(y)
    {
        if(y&1)
            ans=mul(ans,res,n);
        res = mul(res,res,n);
        for(int i =1 ; i<=2 ; i++)
        {
            for(int j =1 ; j<=2 ; j++)
            {
                ans.s[i][j]%=mod;
                res.s[i][j]%=mod;
            }
        }
        y=y>>1;
    }
}

int main()
{
    long long int n=2,y;
    while(scanf("%lld%lld%lld",&a,&b,&y),y||a||b)
    {
        if(y<=2)
        {

            printf("1\n");
            continue;
        }
        y-=3;
        quick(y,n);
        matrix ans0;
        for(int i=1 ;i<=n;i++)
            for(int j=1 ;j<=n ;j++)
                ans0.s[i][j]=0;
        ans0.s[1][1]=1;
        ans0.s[2][1]=1;
        ans0=mul(ans,ans0,n);
       /* for(int i=1 ;i<3 ;i++)
        {
            for(int j=1 ;j<3 ;j++)
                printf("%lld ",ans0.s[i][j]);
            puts("");
        }*/

        printf("%lld\n",ans0.s[1][1]%mod);

    }
    return 0;
}

相关题目：HDU 5950  POJ 3070