C 神奇的数列
总时间限制:1000ms 内存限制:128 MB
问题描述
跳蚤国王最近迷上了一个神奇的数列，Fibonacci 数列，
这个数列有一个非常神奇的性质，我们令 f(i) 表示序列中的第 i 项，
并令 f(1) =1,f(2) = 1, 那么当 i ≥ 3 的时候有 f(i) = f(i − 1) + f(i − 2).
现在跳蚤国王把一坨数放在了一个序列 a 里面，然后他要施行魔法啦 QwQ
操作一：1 l r x，
表示跳蚤国王使用魔法把 [l,r] 的数字都增加了一个x
操作二：2 l r ，
表示跳蚤国王要进行询问，问在序列中 [l,r] 这些数字对应到 Fibonacci 数列中后和是多少啊？
跳蚤国王当然是会这个问题的，但是他想考考你……
答案可能特别特别的大，所以只需要输出对 1000000007 取模后得到的
数组就行啦
输入格式
第一行两个数字 n,m，表示序列中一共有 n 个数字，并且有 m 个操作
接下来一行 n 个数字表示原序列，分别是 a 1 ,a 2 ,...,a n
接下来 m 行，第一个数字是 opt，若 opt = 1 则表示这是操作一，后
面跟上三个数字 l,r,x，表示在区间 l,r 的每个 a i 加上一个 x；若 opt = 2,
则表示这是操作二，后面跟上两个数字 l,r，即题目描述中的询问
输出格式
对于每个操作二，输出一个数字, 就是题目描述中提到的查询的那个东西
样例输入
5 3
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
样例输出
5
7
提示
最开始的时候有 a = {1,1,2,1,1}
对于第一次询问，我们要求的就是
f(a 1 ) + f(a 2 ) + f(a 3 ) + f(a 4 ) +f(a 5 ) = f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5
进行一次操作 1，
现在序列变成了 a = {1,3,4,3,1}
进行一次操作 2，
我们要求的就是 f(a 2 )+f(a 3 )+f(a 4 ) = f(3)+f(4)+f(3) = 2 + 3 + 2 = 7
数据规模与约定：
对于 40% 的数据，有 n ≤ 10,m ≤ 10, 操作一中的 x ≤ 10
对于 100% 的数据，有 n ≤ 10 ^5 ,m ≤ 10 ^5 ，操作一中的 x ≤ 10 ^9
实现代码
#include<cstdio>
using namespace std;
int ci,l,r,x,m,n,k,ans[100000],kim[100005],f[100005];
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%d %d",&n,&m);
f[1]=f[2]=1;
for(int mi=3;mi<=100000;mi++){
f[mi]=f[mi-1]+f[mi-2];
}
for(int mi=1;mi<=n;mi++)
scanf("%d",&kim[mi]);
ci=0;
for(int mi=0;mi<m;mi++){
scanf("%d",&k);
if(k==1){
scanf("%d %d %d",&l,&r,&x);
for(int ni=l;ni<=r;ni++){
kim[ni]+=x;
}
}
if(k==2){
ci=ci+1;
ans[ci]=0;
scanf("%d %d",&l,&r);
for(int ni=l;ni<=r;ni++)
ans[ci]=ans[ci]+f[kim[ni]]%1000000007;
}
}
if(ci>0)
for(int mi=1;mi<=ci;mi++)
printf("%d\n",ans[mi]);
return 0;
}
题解
模拟题还拿不到分数就真的可以去狗带了，但是我也就拿到送出去的一部分分数……
讲道理嘛！！
正解不就是再用矩阵乘法加速嘛…我也知道就是没用啊（那还说什么）
