給出一些數(shù)組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

根據(jù)上面兩個我們就可以知道

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

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

這樣我們就把矩陣構(gòu)造出來了，相當于每次詢問某一段區(qū)間的矩陣的乘積。

由于是連續(xù)的區(qū)間，線段樹即可解決問題。

注意矩陣是放在左邊，所以大的位置放在左邊，線段樹操作的時候也需要注意了。

?

?

召喚代碼君：

?

?

#include <iostream> #include <cstring> #include <cstdio> #define maxn 300300 #define mod 1000000007 typedef 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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lochan/p/3873730.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ3772_Calculate the Function的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。