NYOJ——301递推求值（矩阵快速幂）-白红宇

NYOJ——301递推求值（矩阵快速幂）

阅读量：5019 次

发布时间：2019-06-12

本文共 1355 字，大约阅读时间需要 4 分钟。

递推求值

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述

给你一个递推公式：

f(x)=a*f(x-2)+b*f(x-1)+c

并给你f(1),f(2)的值，请求出f(n)的值，由于f(n)的值可能过大，求出f(n)对1000007取模后的值。

注意:-1对3取模后等于2

输入

第一行是一个整数T,表示测试数据的组数(T<=10000)

随后每行有六个整数，分别表示f(1),f(2),a,b,c,n的值。

其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)

输出

输出f(n)对1000007取模后的值

样例输入

1 1 1 1 0 5

1 1 -1 -10 -100 3

样例输出

999896

之前一直玩二维的，发现三维的矩阵也蛮容易构造的。新编辑器蛮好用。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  using namespace std;typedef long long LL;#define INF 0x3f3f3f3fconst LL mod=1000007;struct mat{ LL pos[3][3]; mat(){memset(pos,0,sizeof(pos));}};inline mat operator*(const mat &a,const mat &b){ int i,j,k; mat c; for (i=0; i<3; i++) { for (j=0; j<3; j++) { for (k=0; k<3; k++) { c.pos[i][j]+=(((a.pos[i][k])%mod)*(b.pos[k][j])%mod+mod)%mod; } } } return c;}inline mat matpow(mat a,LL b){ mat r,bas; r.pos[0][0]=r.pos[1][1]=r.pos[2][2]=1; bas=a; while (b!=0) { if(b&1) r=r*bas; bas=bas*bas; b>>=1; } return r;}int main(void){ ios::sync_with_stdio(false); LL a,b,c,n,f1,f2; int tcase; while (cin>>tcase) { while (tcase--) { cin>>f1>>f2>>a>>b>>c>>n; if(n==1) cout<
                   
                    <