Reincarnation

正因为梦易碎，才格外美好。

CF446C DZY Loves Fibonacci Numbers

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

哪有出题人卡模数的啊（恼。

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/446/C

形式化题意：给定一个有初始权值，长度为 的序列 ，维护 次操作：

  • 对于区间 ，执行 ；
  • 求区间和，对 取模。

其中 表示斐波那契数第 项，其中 。

数据范围：

首先我们尝试通过拆分斐波那契数来找到一些奇妙的性质：

但这个有什么用呢？毕竟有 ，这就和普通的斐波那契数列的公式推导如出一辙，但据此我们可以使用广义斐波那契数列的公式，也就是设：

我们设 ，得到：

然后我们可以得到一个性质是：

推广至广义即可得到：

对于区间加，也就是对整体的答案加上一个 ，这个变量只和 有关，而实际上，在本题中，，也就是当前区间的前两个位置。

维护标记 表示当前的 ，然后通过上面广义斐波那契的公式得到该区间的和即可。

本题还存在一个根号分治的做法，大概是每遇到 个操作后暴力重构整个数列，否则直接根据操作统计答案。这个做法是 的，同样可以通过，比较巧妙。

AC 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
108
109
110
111
112
113
114
115
116
117
118
119
// ----- Eternally question-----
// Problem: DZY Loves Fibonacci Numbers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF446C
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-07-22 19:14:53
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10;
const int Mod=1e9+9;
int N,Q,a[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct St
{
	int l,r;
	ll val,f1,f2;
}Tr[MAXN<<2];
ll f[MAXN];
inline void pushUp(int p)
{ Tr[p].val=(Tr[ls].val+Tr[rs].val)%Mod; }
inline void pushDown(int p,int l,int r)
{
	if(!Tr[p].f1&&!Tr[p].f2) return ;
	int mid=(l+r)>>1,pos=mid-l+2;
	Tr[ls].f1+=Tr[p].f1,Tr[ls].f2+=Tr[p].f2;
	Tr[ls].val+=Tr[p].f2*(f[mid-l+2]-1)+Tr[p].f1*f[mid-l+1];
	Tr[rs].f1+=f[pos-1]*Tr[p].f2+f[pos-2]*Tr[p].f1;
	Tr[rs].f2+=f[pos]*Tr[p].f2+f[pos-1]*Tr[p].f1;
	Tr[rs].val+=Tr[p].f2*(f[r-l+2]-1)+Tr[p].f1*f[r-l+1]-Tr[p].f2*(f[mid-l+2]-1)-Tr[p].f1*f[mid-l+1];
	Tr[ls].f1%=Mod,Tr[ls].f2%=Mod,Tr[ls].val%=Mod;
	Tr[rs].f1%=Mod,Tr[rs].f2%=Mod,Tr[rs].val%=Mod;
	Tr[p].f1=Tr[p].f2=0;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=a[l],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyAdd(int p,int l,int r)
{
	if(Tr[p].l>r||Tr[p].r<l) return ;
	if(l<=Tr[p].l&&Tr[p].r<=r)
	{
		Tr[p].f1+=f[Tr[p].l-l+1],Tr[p].f2+=f[Tr[p].l-l+2];
		Tr[p].val+=f[Tr[p].r-Tr[p].l+1]*f[Tr[p].l-l+1]%Mod+(f[Tr[p].r-Tr[p].l+2]-1)*f[Tr[p].l-l+2]%Mod;
		Tr[p].f1%=Mod,Tr[p].f2%=Mod,Tr[p].val%=Mod;
		return ;
	}
	pushDown(p,Tr[p].l,Tr[p].r);
	modifyAdd(ls,l,r),modifyAdd(rs,l,r);
	pushUp(p);
}
ll querySum(int p,int l,int r)
{
	if(Tr[p].l>r||Tr[p].r<l) return 0;
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	pushDown(p,Tr[p].l,Tr[p].r);
	return (querySum(ls,l,r)+querySum(rs,l,r))%Mod;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),f[1]=f[2]=1;
	for(int i=3;i<=N+1;++i) f[i]=(f[i-1]+f[i-2])%Mod;
	for(int i=1;i<=N;++i) read(a[i]);
	build(1,1,N);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==1) modifyAdd(1,ql,qr);
		else write((querySum(1,ql,qr)+Mod)%Mod,'\n');
	}
	return 0;
}
/*

*/
相关文章