首页 > 代码库 > zoj 3772 Calculate the Function

zoj 3772 Calculate the Function

2024-07-16 06:21:37   220人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5235

这道题需要构造矩阵：F(X)=F(X-1)+F(X-2)*A(X)转化为F(X)*A(X+2)+F(X+1)=F(X+2)，然后在构造矩阵

{1, A[x]}  {F(x+1)}  {F(X+2)}

{1,    0 }*{F(X)    }={F(X+1)}

然后用线段数维护乘号左边的乘积；

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 101000  5 using namespace std;  6 const int mod=1000000007;  7   8 int t,a[maxn*10],n,m;  9 int l,r; 10 struct matrix 11 { 12     long long a[4][4]; 13 }; 14  15 struct node  16 { 17     int l; 18     int r; 19     matrix c; 20 } tree[maxn*4]; 21  22 matrix multi(matrix x,matrix y) 23 { 24     matrix temp; 25     for(int i=1; i<=2; i++) 26     { 27         for(int j=1; j<=2; j++) 28         { 29             temp.a[i][j]=0; 30             for(int k=1; k<=2; k++) 31             { 32                 temp.a[i][j]=(x.a[i][k]*y.a[k][j]+temp.a[i][j])%mod; 33             } 34         } 35     } 36     return temp; 37 } 38  39 matrix build(int i,int l,int r) 40 { 41     tree[i].l=l; 42     tree[i].r=r; 43     if(l==r) 44     { 45         tree[i].c.a[1][1]=1; 46         tree[i].c.a[1][2]=a[l]; 47         tree[i].c.a[2][1]=1; 48         tree[i].c.a[2][2]=0; 49         return tree[i].c; 50     } 51     int mid=(l+r)>>1; 52     build(i<<1,l,mid); 53     build(i<<1|1,mid+1,r); 54     tree[i].c=multi(tree[i<<1|1].c,tree[i<<1].c); 55     return tree[i].c; 56 } 57  58 matrix search1(int i,int l,int r) 59 { 60     if(tree[i].l==l&&tree[i].r==r) 61     { 62         return tree[i].c; 63     } 64     int mid=(tree[i].l+tree[i].r)>>1; 65     if(r<=mid) 66     { 67         return search1(i<<1,l,r); 68     } 69     else if(l>mid) 70     { 71         return search1(i<<1|1,l,r); 72     } 73     else 74     { 75         return multi(search1(i<<1|1,mid+1,r),search1(i<<1,l,mid)); 76     } 77 } 78 int main() 79 { 80     scanf("%d",&t); 81     while(t--) 82     { 83         scanf("%d%d",&n,&m); 84         for(int i=1; i<=n; i++) 85         { 86             scanf("%d",&a[i]); 87         } 88         build(1,1,n); 89         while(m--) 90         { 91             scanf("%d%d",&l,&r); 92             if(r-l>=2) 93             { 94                 matrix tm,ans; 95                 tm.a[1][1]=a[l+1]; 96                 tm.a[2][1]=a[l]; 97                 ans=multi(search1(1,l+2,r),tm); 98                 printf("%lld\n",ans.a[1][1]); 99             }100             else printf("%d\n",a[r]%mod);101         }102     }103     return 0;104 }
View Code

 


联系
我们