Codeforces 718C C. Sasha and Array
13326 단어 Codeforces
time limit per test5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Sasha has an array of integers a1, a2, …, an. You have to perform m queries. There might be queries of two types:
1 l r x — increase all integers on the segment from l to r by values x; 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7. In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.
Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?
Input The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of elements in the array and the number of queries respectively.
The next line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109).
Then follow m lines with queries descriptions. Each of them contains integers tpi, li, ri and may be xi (1 ≤ tpi ≤ 2, 1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 109). Here tpi = 1 corresponds to the queries of the first type and tpi corresponds to the queries of the second type.
It’s guaranteed that the input will contains at least one query of the second type.
Output For each query of the second type print the answer modulo 109 + 7.
Examples
input
5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5
output
5
7
9
Note
Initially, array a is equal to 1, 1, 2, 1, 1.
The answer for the first query of the second type is f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5.
After the query 1 2 4 2 array a is equal to 1, 3, 4, 3, 1.
The answer for the second query of the second type is f(3) + f(4) + f(3) = 2 + 3 + 2 = 7.
The answer for the third query of the second type is f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9.
#include
#define mo 1000000007
using namespace std;
int n,m;
int a[100005];
struct ma{
int x[2][2];
ma operator *(const ma p)const{
ma ans;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)ans.x[i][j]=0;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)ans.x[i][k]=(ans.x[i][k]+1LL*x[i][j]*p.x[j][k])%mo;
return ans;
}
ma operator +(const ma p)const{
ma ans;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)ans.x[i][j]=0;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)ans.x[i][j]=(x[i][j]+p.x[i][j])%mo;
return ans;
}
ma pow(int k){
ma ans,now;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++)ans.x[i][j]=0,now.x[i][j]=x[i][j];
ans.x[i][i]=1;
}
for(;k;k>>=1){
if(k&1)ans=ans*now;
now=now*now;
}
return ans;
}
bool operator ==(const ma k)const{
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)if(k.x[i][j]!=x[i][j])return false;
return true;
}
}f,st;
struct tree{
ma m,a;
void pushup(tree l,tree r){m=l.m+r.m;}
void add(int k){m=m*f.pow(k);a=a*f.pow(k);}
void add(ma k){m=m*k;a=a*k;}
}t[400005];
#define lson index<<1
#define rson index<<1|1
#define mid ((l+r)>>1)
void pushdown(int index){
if(!(t[index].a==st)){
t[lson].add(t[index].a);
t[rson].add(t[index].a);
t[index].a=st;
}
}
void build(int l,int r,int index){
t[index].a=st;
if(l==r){t[index].m=f.pow(a[l]);return;}
build(l,mid,lson);
build(mid+1,r,rson);
t[index].pushup(t[lson],t[rson]);
}
void add(int L,int R,int l,int r,int index,ma x){
if((L<=l)&&(R>=r)){t[index].add(x);return;}
pushdown(index);
if(L<=mid)add(L,R,l,mid,lson,x);
if(R>mid)add(L,R,mid+1,r,rson,x);
t[index].pushup(t[lson],t[rson]);
}
inline ma query(int L,int R,int l,int r,int index){
if((L<=l)&&(R>=r))return t[index].m;
pushdown(index);
if(R<=mid)return query(L,R,l,mid,lson);
if(L>mid)return query(L,R,mid+1,r,rson);
ma ans=query(L,R,l,mid,lson)+query(L,R,mid+1,r,rson);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
f.x[1][0]=1;f.x[0][1]=1;f.x[1][1]=1;
st.x[1][1]=1;st.x[0][0]=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,n,1);
while(m--){
int flag,l,r,x;
scanf("%d",&flag);
if(flag==1){
scanf("%d%d%d",&l,&r,&x);
add(l,r,1,n,1,f.pow(x));
}else{
scanf("%d%d",&l,&r);
ma tmp=query(l,r,1,n,1);
printf("%d
",tmp.x[1][0]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.