HDU 5950 Recursive sequence (矩阵快速幂）1/5

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950

2018 年10 月30日      本周第一篇解题报告  （解题报告计划，第二周）

Problem Description

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.

Output

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

Sample Input

2 3 1 2 4 1 10

Sample Output

85 369

Hint

In the first case, the third number is 85 = 2*1十2十3^4. In the second case, the third number is 93 = 2*1十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.

Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

题面如上，看Hint很容易发现这是个递推，公式为 f（n）= f ( n -2 )*2+f( n -1) + n *n *n*n . 

题目的数据很大，那么就考虑使用矩阵快速幂来解决。这题的难点在于，系数矩阵的推导（话说做过类似的题的话，就不算难点了）。首先分析上边的系数矩阵，发现前两项很好构造，那么考虑最后一项，n的四次方如何构造。

系数矩阵的构造，参考这篇文章：https://blog.csdn.net/u012061345/article/details/52224623

最后，构造出的系数矩阵为：

1 0 0 0 0 0 0        1               1

1 1 0 0 0 0 0        i                i+1

1 2 1 0 0 0 0       i2              (i+1)2

1 3 3 1 0 0 0  *   i3     =       (i+1)3

1 4 6 4 1 0 0       i4               (i+1)4

0 0 0 0 0 0 1       f[i-2]           f[i-1]

0 0 0 0 1 2 1      f[i-1]             f[i]

值得一提的是，对于上式的乘法，不需要单独写一个额外的矩阵乘法，只需要把非7阶方阵的矩阵补成方阵就好，简单来说就是把其余的置为0。

代码 ：

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

};
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];
                    C.s[i][j]%=2147493647;
                }
    return C;
}
void quick(long long int y,long long int n)
{
    for(long long int i = 1 ; i<= n ; i++)
        for(long long int j = 1 ; j<=n ; j++)
        {
                ans.s[i][j]=0;
        }
    //核心     系数矩阵
    ans.s[1][1]=1;
    ans.s[2][1]=1; ans.s[2][1]=1; ans.s[2][2]=1;

    ans.s[3][1]=1;  ans.s[3][2]=2; ans.s[3][3]=1;
    ans.s[4][1]=1;  ans.s[4][2]=3; ans.s[4][3]=3; ans.s[4][4]=1;
    ans.s[5][1]=1;  ans.s[5][2]=4; ans.s[5][3]=6; ans.s[5][4]=4; ans.s[5][5]=1;

    ans.s[6][7]=1;
    ans.s[7][5]=1;  ans.s[7][6]=2;  ans.s[7][7]=1;

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

int main()
{
    long long int n=7,y,a,b;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&y,&a,&b);
        if(y==1)
        {
            printf("%lld\n",a);
            continue;
        }
        if(y==2)
        {
           printf("%lld\n",b);
            continue;
        }

        y-=2;

        quick(y,n);
        matrix ans0;
        for(long long int i = 1 ; i<= n ; i++)
            for(long long int j = 1 ; j<=n ; j++)
                ans0.s[i][j]=0;

        ans0.s[1][1]= 1 ;
        ans0.s[2][1]= 3 ;
        ans0.s[3][1]= 9 ;
        ans0.s[4][1]= 27;
        ans0.s[5][1]= 81;
        ans0.s[6][1]= a;
        ans0.s[7][1]= b;

        ans0=mul(ans,ans0,n);
        printf("%lld\n",ans0.s[6][1]%2147493647);//此处ans0实际为第n+1个矩阵，这里取ans0里边f(n+1-1)的那个值
    }
}