2016ACM/ICPC亚洲区沈阳站1003题 Recursive sequence +构造矩阵+矩阵连乘

清疚 2022-07-15 02:42 150阅读 0赞

题目链接：[http://acm.hdu.edu.cn/contests/contest\_showproblem.php?pid=1003&cid=733][http_acm.hdu.edu.cn_contests_contest_showproblem.php_pid_1003_cid_733]

题面描述：

# Recursive sequence #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 98 Accepted Submission(s): 46**

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.

题目大意：

由题意可以得到F\[N\]=F\[N-1\]+2\*F\[N-2\]+N^4 ，求F\[N\]。

题目分析：

由于数据比较大，必须采用构造矩阵的方法，可以得到\[Fn, Fn-1, (n+1)^4, (n+1)^3, (n+1)^2, (n+1), 1\]=

x=  
\{  
0,0,0,0,0,0,0,0,  
0,1,2,1,0,0,0,0,  
0,1,0,0,0,0,0,0,  
0,0,0,1,4,6,4,1,  
0,0,0,0,1,3,3,1,  
0,0,0,0,0,1,2,1,  
0,0,0,0,0,0,1,1,  
0,0,0,0,0,0,0,1  
\};

乘以\[Fn-1, Fn-2, n^4, n^3, n^2, n, 1\]可以得到。最后求解F\[n\]即可。

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const long long mod=2147493647;
    
    long long n;
    
    typedef struct
    {
        long long m[8][8];
    }mat;
    ///需要输入的矩阵
    mat x=
    {
        0,0,0,0,0,0,0,0,
        0,1,2,1,0,0,0,0,
        0,1,0,0,0,0,0,0,
        0,0,0,1,4,6,4,1,
        0,0,0,0,1,3,3,1,
        0,0,0,0,0,1,2,1,
        0,0,0,0,0,0,1,1,
        0,0,0,0,0,0,0,1
    };
    
    mat I;///单位阵，根据阶数来确定
    
    mat multi(mat a,mat b)
    {
        mat c;
        memset(c.m,0,sizeof(c.m));
        for(int i=1; i<=7; i++)
        {
            for(int j=1; j<=7; j++)
            {
                if(a.m[i][j])///加速算法,一定要进行初始化,否则没有效果
                {
                    for(int k=1; k<=7; k++)
                        c.m[i][k]+=((a.m[i][j]%mod)*(b.m[j][k]%mod))%mod;
                }
            }
        }
        return c;
    }
    
    mat power(mat A,long long k)//矩阵快速幂
    {
        mat ans=I,p=A;
        while(k)
        {
            if(k&1)///若k为奇数,
            {
                ans=multi(ans,p);
                k--;
            }
            k>>=1;///k=k/2;
            p=multi(p,p);
        }
        return ans;
    }
    
    int main()
    {
        long long t;
        long long a,b;
        while(scanf("%lld",&t)!=EOF)
        {
            while(t--)
            {
                scanf("%lld%lld%lld",&n,&a,&b);
                if(n==1)
                {
                    printf("%lld\n",a);
                }
                else if(n==2)
                {
                    printf("%lld\n",b);
                }
                else
                {
                    for(int i=1; i<=7; i++)
                    {
                        I.m[i][i]=1;
                    }
                    /*for(int i=1; i<=7; i++)
                    {
                        for(int j=1; j<=7; j++)
                        {
                            cout<<x.m[i][j]<<" ";
                        }
                        cout<<endl;
                    }*/
                    mat anss=power(x,n-2);
                   /* for(int i=1; i<=7; i++)
                    {
                        for(int j=1; j<=7; j++)
                        {
                            cout<<anss.m[i][j]<<" ";
                        }
                        cout<<endl;
                    }*/
                    long long summ=((anss.m[1][1]*b)%mod+(anss.m[1][2]*a)%mod+(anss.m[1][3]*81)%mod+(anss.m[1][4]*27)%mod+(anss.m[1][5]*9)%mod+(anss.m[1][6]*3)%mod+anss.m[1][7]%mod)%mod;
                    printf("%lld\n",summ);
                }
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_contests_contest_showproblem.php_pid_1003_cid_733]: http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=733