【JZ雅礼联考】斐波那契 题解

OI/XCPC , , Comments

题目大意

  定义Fibonacci数列为：$F[1]=1;~F[2]=1;~F[n]=F[n-1]+F[n-2]~(n>2)$
  现有一个n个元素的数列$a$，进行m个操作，操作类型如下：
  1 L R$~$表示给$a_i$加上$F[i-L+1]$，其中 L<=i<=R
  2 L R$~$表示询问$\sum_{i=L}^Ra_i~mod~(10^9+9)$
  1<=n, m<=10^5

【40%】n,m<=1000

  $O(nm)$暴力

【100%解法1】n,m<=10^5

  考虑平衡规划（定期重构），把修改操作储存起来，储到了$\sqrt{n}$个修改的时候更新原序列。
  修改更新原序列：每个位置维护一个二元组$(x,y)$，$x$表示它前一个元素的增加量，$y$表示自己的增加量。对于第 j 个修改$L_j$~$R_j$，我们使$y_{L_j}+=1$，$x_{R_j+1}-=F[Len_j]$，$y_{R_j+1}-=F[Len_j+1]$。（这个类似于+1-1标记）。然后做一遍类似Fibonacci一样的循环：$x_i+=y_{i-1}$，$y_i+=x_{i-1}+y_{i-1}$。这样，我们就处理出了每个元素的增加量，最后$a_i+=y_i$。
  询问：此时还剩下的修改操作在$\sqrt{n}$个以内，我们可以对剩下的每一个修改操作直接计算出对答案的贡献，最后加上原序列的前缀和即可。
  时间复杂度$O(m\sqrt{n})$

【100%解法1.5】

  解法1的修改我们维护的是一个二元组，其实每个位置维护一个值就行了。这算是个优化吧。

【100%解法2】

  我们要知道这么些东西：
  1、若$H_1=a$，$H_2=b$，$H_n=H_{n-1}+H_{n-2}$，则$H_n=aF_{n-2}+bF_{n-1}$。
  2、推广一下，对于$H_1=a$、$H_2=b$的类Fibonacci数列，满足$\sum_{i=1}^nH_i=H_{n+2}-b$
  因此我们只需知道数列的前两项就可以快速求和。
  用线段树维护区间内的数列的前两项。
  时间复杂度$O(m\log n)$

【100%解法3】

  我们知道Fibonacci数列是有通项公式的。
  科普：对于形如$F_n=pF_{n-1}+qF_{n-2}$的递推数列，令$x^2=px+q$，若该方程有两个不同的实数根$x_1$和$x_2$，则$F_n$的通项公式一定可以表示成$F_n=αx_1^n+βx_2^n$的形式
  事实上，在本题的模意义下，$F[n]≡276601605*(691504013^n − 308495997^n)$。
  于是任务变成维护两个等比数列。因为两个公比相同的等比数列可以直接相加，所以维护数列的首项即可。这个可以用线段树解决。
  时间复杂度$O(m \log n)$

解法1代码

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=(1e5)+5;
const LL mo=(1e9)+9;

int n,sqrtn,m;
LL a[maxn],Sa[maxn],f[maxn],Sf[maxn];

int mdf[maxn][2],m0;
LL d[maxn][2];
int main()
{
	f[1]=f[2]=1;
	Sf[1]=1, Sf[2]=2;
	fo(i,3,maxn-5) f[i]=(f[i-1]+f[i-2])%mo, Sf[i]=(Sf[i-1]+f[i])%mo;
	
	scanf("%d %d",&n,&m);
	sqrtn=sqrt(n);
	fo(i,1,n) scanf("%lld",&a[i]), Sa[i]=(Sa[i-1]+a[i])%mo;
	
	while (m--)
	{
		int ty,l,r;
		scanf("%d %d %d",&ty,&l,&r);
		
		if (ty==1)
		{
			mdf[++m0][0]=l, mdf[m0][1]=r;
			if (m0==sqrtn)
			{
				memset(d,0,sizeof(d));
				fo(i,1,m0)
				{
					d[mdf[i][0]][1]=(d[mdf[i][0]][1]+1)%mo;
					int len=mdf[i][1]-mdf[i][0]+1;
					d[mdf[i][1]+1][0]=(d[mdf[i][1]+1][0]-f[len]+mo)%mo;
					d[mdf[i][1]+1][1]=(d[mdf[i][1]+1][1]-f[len+1]+mo)%mo;
				}
				fo(i,1,n)
				{
					d[i][0]=(d[i][0]+d[i-1][1])%mo;
					d[i][1]=(d[i][1]+d[i-1][0]+d[i-1][1])%mo;
				}
				fo(i,1,n) a[i]=(a[i]+d[i][1])%mo, Sa[i]=(Sa[i-1]+a[i])%mo;
				m0=0;
			}
		} else
		{
			LL ans=(Sa[r]-Sa[l-1]+mo)%mo;
			fo(i,1,m0)
			{
				int tl=max(l,mdf[i][0]), tr=min(r,mdf[i][1]);
				if (tl<=tr)
				{
					int ttl=tl-mdf[i][0]+1, ttr=ttl+tr-tl;
					ans=(ans+ Sf[ttr]-Sf[ttl-1]+mo )%mo;
				}
			}
			
			printf("%lld\n",ans);
		}
	}
}

解法2代码来自LZH

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
#include<cstdio>
#define min(x, y) ((x)<(y)?(x):(y))
#define max(x, y) ((x)<(y)?(y):(x))

const int N= 100005, K= 131072, P= 1e9+9;
int num[K*2][2], sum[K*2], f[N][2], s[N][2];
int a[N], c[20];
int n, m, k, x, y, ans;


void join(int q, int p, int t){
	sum[t]= (sum[t]+ ((long long)s[min(p, y)-x+1][0] - s[max(0, q-x)][0]+P + s[min(p, y)-x+1][1] - s[max(0, q-x)][1]+(long long)P) % P ) % P;
	if(x<=q && p<=y){
		num[t][0]= (num[t][0]+(long long)f[q-x+1][0]+f[q-x+1][1])%P;
		num[t][1]= (num[t][1]+(long long)f[q-x+2][0]+f[q-x+2][1])%P;
		return;
	}
	int mid= (q+p)>>1;
	if(x<=mid) join(q, mid, t<<1);
	if(y>mid) join(mid+1, p, t<<1|1);
}

void find(int q, int p, int t){
	if(x<=q && p<=y){
		ans= (ans+sum[t])%P;
		return;
	}
	ans= (ans+num[t][0]*(s[min(p, y)-q+1][0]-(long long)s[max(0, x-q)][0]+P))%P;
	ans= (ans+num[t][1]*(s[min(p, y)-q+1][1]-(long long)s[max(0, x-q)][1]+P))%P;
	int mid= (q+p)>>1;
	if(x<=mid) find(q, mid, t<<1);
	if(y>mid) find(mid+1, p, t<<1|1);
}

int read(){
	register char ch;
	register int x;
	for(ch= getchar(); ch<'0' || ch>'9'; ch= getchar());
	for(x= ch-'0', ch= getchar(); ch>='0' && ch<='9'; x= x*10+ch-'0', ch= getchar());
	return x;
}

int main(){
	n= read(); m= read();
	for(register int i= 1; i<=n; i++) a[i]= (a[i-1]+read())%P;
	f[1][0]= f[2][1]= 1; s[1][0]= s[2][1]= s[2][0]= 1;
	for(register int i= 2; i<=n; i++){
		f[i+1][0]= (f[i][0]+ f[i-1][0])%P;
		f[i+1][1]= (f[i][1]+ f[i-1][1])%P;
		s[i+1][0]= (f[i+1][0]+ s[i][0])%P;
		s[i+1][1]= (f[i+1][1]+ s[i][1])%P;
	}
	for(int i= 1; i<=m; i++){
		k= read(); x= read(); y= read();
		if(k==1){
			join(1, K, 1);
		}else{
			ans= 0;
			find(1, K, 1);
			ans= ((long long)ans+a[y]-a[x-1]+P+P)%P;
			printf("%d\n", ans);
		}
	}
	return 0;
}

参考资料：Johann写的题解
引用：lzh大神的代码

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许