Description
给定一个长度为 N 的序列 A={a1,a2,…,an} .
M 次操作, 每次操作形如下面两种中的一种:
1 l r x 将 a l , a l + 1 , . . . , a r a_l,a_{l+1},...,a_r al,al+1,...,ar 都加上 x ;
2 l r 求 ∑ i = l r f ( a i ) m o d ( 1 0 9 + 7 ) sum_{i=l}^rf(a_i) mod (10^9+7) ∑i=lrf(ai) mod (109+7)
其中 f n f_n fn 为斐波那契数列的第 n 项, 即
{ f n = 1 n = 1 或 n = 2 f n = f n − 1 + f n − 2 n > 2 left { begin{array}{ll} f_n=1qquadqquadqquad n=1或n=2\ f_n=f_{n-1}+f_{n-2}qquad n>2 end{array} right. {fn=1 n=1或n=2fn=fn−1+fn−2n>2
Input
第一行两个数 N,M .
第二行 N 个数 a1,a2,…,an .
接下来 M 行, 每行代表题目描述中的一种操作.
Output
对于每个询问, 输出一行, 表示答案.
Solution
这题是区间修改查询，一看就是线段树，但我们怎么处理序号加x呢？
众所周知，斐波那契数列可以用矩阵快速幂来搞。
所以，我们可以让线段树每一个节点储存一个表示
f
(
a
i
)
f(a_i)
f(ai)的矩阵，对于某个节点加x，只要用这个节点的矩阵乘上单位矩阵p的x次方。
那么问题来了，虽然可以处理单点，但区间怎么办？
其实对于一段区间，我们可以直接将矩阵每一位的值加起来再乘（即结合律），举个栗子：
[ f ( 2 ) f ( 3 ) 0 0 ] ∗ [ 0 1 1 1 ] + [ f ( 4 ) f ( 5 ) 0 0 ] ∗ [ 0 1 1 1 ] quadbegin{bmatrix} f(2)&f(3) \\ 0&0 end{bmatrix} quad * quad begin{bmatrix} 0&1 \\ 1&1 end{bmatrix} quad+quadbegin{bmatrix} f(4)&f(5) \\ 0&0 end{bmatrix} quad*quadbegin{bmatrix} 0&1 \\ 1&1 end{bmatrix}quad ⎣⎡f(2)0f(3)0⎦⎤∗⎣⎡0111⎦⎤+⎣⎡f(4)0f(5)0⎦⎤∗⎣⎡0111⎦⎤
= [ f ( 2 ) + f ( 4 ) f ( 3 ) + f ( 5 ) 0 0 ] ∗ [ 0 1 1 1 ] = begin{bmatrix} f(2)+f(4)&f(3)+f(5) \\ 0&0 end{bmatrix}quad*quadbegin{bmatrix} 0&1 \\ 1&1 end{bmatrix} =⎣⎡f(2)+f(4)0f(3)+f(5)0⎦⎤∗⎣⎡0111⎦⎤
= [ f ( 3 ) + f ( 5 ) f ( 4 ) + f ( 6 ) 0 0 ] = begin{bmatrix} f(3)+f(5)&f(4)+f(6 ) \\ 0&0 end{bmatrix} =⎣⎡f(3)+f(5)0f(4)+f(6)0⎦⎤
那么线段树统计区间直接将矩阵加起来就好啦。
因为常数较大，所以要适当卡常，而且应提前处理好每次加x乘的矩阵，保证复杂度。
但是似乎出题人预处理了2的幂，所以跑得比我快。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107#include<bits/stdc++.h> using namespace std; const long long mod=1e9+7; long long s[400010]; bool islaz[400010]; struct node{ long long a[3][3]; node(){ memset(a,0,sizeof(a)); } }pp,p,p1,tree[400010],laz[400010]; node func(node a,node b){ node c; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod; return c; } void build(int id,int l,int r){ if(l==r){ p=pp; laz[id]=node(); int x=s[l]-1; tree[id].a[1][2]=1; while(x>0){ if(x%2==1) tree[id]=func(tree[id],p); p=func(p,p); x/=2; } return; } int mid=(l+r)>>1; build(id*2,l,mid); build(id*2+1,mid+1,r); for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) tree[id].a[i][j]=(tree[id*2].a[i][j]+tree[id*2+1].a[i][j])%mod; } void pushdown(int id){ if(islaz[id]){ islaz[id]=0; tree[id*2]=func(tree[id*2],laz[id]); tree[id*2+1]=func(tree[id*2+1],laz[id]); if(islaz[id*2]) laz[id*2]=func(laz[id*2],laz[id]); else laz[id*2]=laz[id],islaz[id*2]=1; if(islaz[id*2+1]) laz[id*2+1]=func(laz[id*2+1],laz[id]); else laz[id*2+1]=laz[id],islaz[id*2+1]=1; laz[id]=node(); } } void update(int id,int l,int r,int ul,int ur){ if(ul<=l&&r<=ur){ tree[id]=func(tree[id],p1); if(islaz[id]) laz[id]=func(laz[id],p1); else laz[id]=p1,islaz[id]=1; return; } pushdown(id); int mid=(l+r)>>1; if(ul<=mid) update(id*2,l,mid,ul,ur); if(ur>mid) update(id*2+1,mid+1,r,ul,ur); for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) tree[id].a[i][j]=(tree[id*2].a[i][j]+tree[id*2+1].a[i][j])%mod; } int query(int id,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return tree[id].a[1][2]%mod; pushdown(id); int mid=(l+r)>>1,sum=0; if(ql<=mid) sum=(sum+0ll+query(id*2,l,mid,ql,qr)%mod)%mod; if(qr>mid) sum=(sum+0ll+query(id*2+1,mid+1,r,ql,qr)%mod)%mod; return sum; } inline int read(){ char c=getchar(); long long x=0,f=1; while(!isdigit(c) && c!='-') c=getchar(); if(c=='-') { f=-1; c=getchar(); } while(isdigit(c)) { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } return x*f; } int main(){ int n,m,op,l,r,x; n=read(),m=read(); for(int i=1;i<=n;i++) s[i]=read(); pp.a[1][2]=pp.a[2][1]=pp.a[2][2]=1; build(1,1,n); for(int i=1;i<=m;i++){ op=read(),l=read(),r=read(); if(op==1){ x=read(); p1=pp; p=pp; int x1=x-1; while(x1>0){ if(x1%2==1) p1=func(p1,p); p=func(p,p); x1/=2; } update(1,1,n,l,r); } else printf("%dn",query(1,1,n,l,r)); } }
最后
以上就是阔达薯片最近收集整理的关于noip2019集训测试赛（四）A.fibonacciDescriptionInputOutputSolutionCode的全部内容，更多相关noip2019集训测试赛（四）A内容请搜索靠谱客的其他文章。
发表评论 取消回复