首页 > 代码库 > ZOJ3772_Calculate the Function

ZOJ3772_Calculate the Function

2024-07-14 12:04:09   223人阅读

给出一些数组a[i]，每次询问为li,ri，定义f[li]=a[li],f[li+1]=a[li+1]，对于其他不超过ri的位置，f[x]=f[x-1]+a[x]*f[x-2] 。

题目有着浓浓的矩阵气息。

f[x]=f[x-1]+a[x]*f[x-2] 

f[x-1]=f[x-1]+0

根据上面两个我们就可以知道

f[x]=========|1,a[x]|         f[x-1]

f[x-1]=======|1 ,  0|         f[x-2]

这样我们就把矩阵构造出来了，相当于每次询问某一段区间的矩阵的乘积。

由于是连续的区间，线段树即可解决问题。

注意矩阵是放在左边，所以大的位置放在左边，线段树操作的时候也需要注意了。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#define maxn 300300#define mod 1000000007typedef long long ll;using namespace std;class Mat{public:    ll f[2][2];    Mat() { f[0][0]=f[1][1]=f[0][1]=f[1][0]=0; }    Mat(int f1,int f2,int f3,int f4){        f[0][0]=f1,f[0][1]=f2,f[1][0]=f3,f[1][1]=f4;    }    Mat operator * (Mat m1) const{        Mat m0;        for (int i=0; i<2; i++)            for (int j=0; j<2; j++)                for (int k=0; k<2; k++)                    m0.f[i][j]=(m0.f[i][j]+f[i][k]*m1.f[k][j])%mod;        return m0;    }    void output(){        cout<<f[0][0]<<‘ ‘<<f[0][1]<<‘\n‘<<f[1][0]<<‘ ‘<<f[1][1]<<‘\n‘;    }}tree[maxn];int n,m,T,a[maxn];void build(int rt,int l,int r){    if (l==r){        tree[rt]=Mat(1,a[l],1,0);        return;    }    int mid=(l+r)>>1;    build(rt<<1,l,mid);    build(rt<<1|1,mid+1,r);    tree[rt]=tree[rt<<1|1]*tree[rt<<1];}Mat query(int rt,int l,int r,int L,int R){    if (L<=l && R>=r) return tree[rt];    int mid=(l+r)>>1;    Mat tot(1,0,0,1);    if (R> mid) tot=query(rt<<1|1,mid+1,r,L,R);    if (L<=mid) tot=tot*query(rt<<1,l,mid,L,R);    return tot;}int main(){    int x,y;    scanf("%d",&T);    while (T--)    {        scanf("%d%d",&n,&m);        for (int i=1; i<=n; i++) scanf("%d",&a[i]);        build(1,1,n);        while (m--)        {            scanf("%d%d",&x,&y);            if (y==x || y==x+1){                if (y==x) printf("%d\n",a[x]);                    else printf("%d\n",a[x+1]);                continue;            }            Mat tmp=query(1,1,n,x+2,y);            /*            cout<<" ans Mat is : \n";            tmp.output();            cout<<" ...........   the end of Mat.";            */            printf("%d\n",(int)((tmp.f[0][0]*a[x+1]+tmp.f[0][1]*a[x])%mod));        }    }    return 0;}

 


联系
我们