矩阵快速幂 F[n]=F[n-2]*2+F[n-1]+i^4 hdu5950

这道题的难点就是构造出这个矩阵

　假如是这样的一个式子 F[n]=F[n-2]*2+F[n-1]，那就很简单

　但是，多了个i^4，这就很难办了。

　所以，我们要着重处理的就是这一部分

　那么 (n+1)^4 = n^4 + 4n^3 + 6n^2 + 4n + 1

             ans.a[][]=bb%mod;///f(i-1)

             ans.a[][]=aa%mod;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

假如目前我们处理的基础矩阵为这个样子。

那么我们就需要以下这样一个与他相乘的矩阵

1 2 1 0 0 0 0 f(2)

1 0 0 0 0 0 0 　 f(1)

0 0 1 4 6 4 1 81

0 0 0 1 3 3 1 27

0 0 0 0 1 2 1　 9

0 0 0 0 0 1 1 3

0 0 0 0 0 0 1 1

代码如下：

 #include<cstdio>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 using namespace std;

 typedef long long ll;

 const ll mod=;

 struct node

 {

     ll a[][];

 }ans,A,B;

 node mat(node x,node y)

 {

     node c;

     for(int i=;i<=;i++)

     for(int j=;j<=;j++)

         c.a[i][j]=;

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)

         for(int k=;k<=;k++)

             c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;

     return c;

 }

 void init()

 {

     A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;

     A.a[][]=;A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;

     A.a[][]=,A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;

     A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;

     A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;A.a[][]=;

     A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;A.a[][]=;

     A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=,A.a[][]=;A.a[][]=;

 }

 void quick_mod(ll n)

 {

     memset(ans.a,,sizeof(ans.a));

     for(int i=;i<=;i++)

     for(int j=;j<=;j++)

         if(i==j) B.a[i][j]=;

         else B.a[i][j]=;

     init();

     while(n){

         if(n&) B=mat(B,A);

         A=mat(A,A);

         n>>=;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

         ll n,aa,bb;

         scanf("%lld%lld%lld",&n,&aa,&bb);

         if(n==) printf("%lld\n",aa);

         else if(n==) printf("%lld\n",bb);

         else{

             quick_mod(n-);

             ans.a[][]=bb%mod;///f(i-1)

             ans.a[][]=aa%mod;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

             ans.a[][]=;

             ans=mat(B,ans);

             printf("%lld\n",ans.a[][]);

         }

     }

     return ;

 }

巴特西

矩阵快速幂 F[n]=F[n-2]*2+F[n-1]+i^4 hdu5950

最新文章

热门文章