首页 > 代码库 > ZOJ3772_Calculate the Function
ZOJ3772_Calculate the Function
给出一些数组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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。