zoj3772Calculate the Function(矩阵+线段树）

表达式类似于斐波那契但是多了一个变量不能用快速幂来解不过可以用线段树进行维护

对于每一个点够一个2*2的矩阵

1 a[i]

1 0 这个矩阵应该不陌生类似于构造斐波那契的那个数列还是比较容易能想到的

然后就用线段树进行维护注意矩阵不满足交换律在乘的时候要倒序。

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 100010
 12 #define LL long long
 13 #define INF 0xfffffff
 14 #define mod 1000000007
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 struct Mat
 19 {
 20     LL c[2][2];
 21 }s[N<<2];
 22 LL o[N];
 23 Mat operator * (Mat a,Mat b)
 24 {
 25     Mat c;
 26     memset(c.c,0,sizeof(c.c));
 27     int i,j,k;
 28     for(k =0 ; k < 2 ; k++)
 29     {
 30         for(i = 0 ; i < 2 ;i++)
 31         {
 32             if(a.c[i][k]==0) continue;//优化
 33             for(j = 0 ;j < 2 ;j++)
 34             {
 35                 if(b.c[k][j]==0) continue;//优化
 36                 c.c[i][j] = (c.c[i][j]+a.c[i][k]*b.c[k][j])%mod;
 37             }
 38         }
 39     }
 40     return c;
 41 }
 42 void up(int w)
 43 {
 44    s[w] = s[w<<1|1]*s[w<<1];
 45 }
 46 void build(int l,int r,int w)
 47 {
 48     if(l==r)
 49     {
 50         s[w].c[0][0] = s[w].c[1][0] = 1;
 51         s[w].c[0][1] = o[l];
 52         s[w].c[1][1] = 0;
 53         return ;
 54     }
 55     int m = (l+r)>>1;
 56     build(l,m,w<<1);
 57     build(m+1,r,w<<1|1);
 58     up(w);
 59 }
 60 Mat getsum(int a,int b,int l,int r,int w)
 61 {
 62     if(a<=l&&b>=r)
 63     {
 64         return s[w];
 65     }
 66     int m = (l+r)>>1,i,j;
 67     Mat c;
 68     for(i=0 ;i < 2 ; i++)
 69     {
 70         for(j = 0 ;j < 2 ; j++)
 71         {
 72             if(i==j)
 73             c.c[i][j] = 1;
 74             else
 75             c.c[i][j] = 0;
 76         }
 77     }
 78     if(b>m)
 79     c=c*getsum(a,b,m+1,r,w<<1|1);
 80     if(a<=m)
 81     c=c*getsum(a,b,l,m,w<<1);
 82     return c;
 83 
 84 }
 85 int main()
 86 {
 87     int i,n,m,t;
 88     cin>>t;
 89     while(t--)
 90     {
 91         scanf("%d%d",&n,&m);
 92         for(i = 1 ;i <= n; i++)
 93         scanf("%lld",&o[i]);
 94         build(1,n,1);
 95         while(m--)
 96         {
 97             int a,b;
 98             scanf("%d%d",&a,&b);
 99             if(b-a<=1)
100             {
101                 printf("%lld
",o[b]%mod);
102                 continue;
103             }
104             Mat x;
105             x.c[0][0] = o[a+1];
106             x.c[1][0] = o[a];
107             x.c[0][1] = 1;x.c[1][1] = 0;
108             Mat y = getsum(a+2,b,1,n,1);
109             x = y*x;
110             printf("%lld
",(x.c[0][0])%mod);
111         }
112     }
113     return 0;
114 }

View Code