题目传送门:http://codeforces.com/contest/718/problem/C
数据生成器:http://paste.ubuntu.com/23296960/
官方题解:http://codeforces.com/blog/entry/47314
斐波那契数列的话,转移可以用快速幂
于是用线段树来维护转移矩阵就可以辣!
值得一提的是:我之前一直以为斐波那契数列的通项公式没有用
然而鏼爷讲了二次剩余之后,发现其实拿货是可以出成题目考的QAQ
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200000+9; const int MOD = 1000000007; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int n,m,arr[N]; struct Matrix{ int a[3][3]; inline Matrix() {} inline Matrix(int w) { memset(a,0,sizeof(a)); a[1][1] = a[2][2] = w; } inline Matrix(const Matrix &B) { memcpy(this,&B,sizeof(B)); } inline Matrix operator * (const Matrix &B) { Matrix ret(0); for (int i=1;i<=2;i++) { for (int j=1;j<=2;j++) { for (int k=1;k<=2;k++) { ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD; ret.a[i][j] %= MOD; } } } return ret; } inline Matrix operator ^ (LL t) { Matrix ret(1),w(*this); while (t) { if (t & 1) ret = ret * w; w = w * w; t >>= 1; } return ret; } }trans,cur_trans,ori(1); namespace Segment_Tree{ #define SEG Segment_Tree int ch[N][2],cnt,root,L,R,ans_tmp; Matrix mat[N],tag[N]; inline void maintain(int w){ for (int i=1;i<=2;i++) { for (int j=1;j<=2;j++) { mat[w].a[i][j] = mat[ch[w][0]].a[i][j] + mat[ch[w][1]].a[i][j]; mat[w].a[i][j] %= MOD; } } } inline void push_down(int w) { for (int i=0;i<2;i++) { tag[ch[w][i]] = tag[ch[w][i]] * tag[w]; mat[ch[w][i]] = mat[ch[w][i]] * tag[w]; } tag[w] = Matrix(1); } void Build(int &w, int l, int r) { w = ++cnt; tag[w] = Matrix(1); if (l == r) { mat[w].a[1][1] = mat[w].a[2][1] = 1; mat[w] = mat[w] * (trans^(arr[l]-1)); } else { int mid = l + r + 1 >> 1; Build(ch[w][0],l,mid-1); Build(ch[w][1],mid,r); maintain(w); } } void Modify(int w, int l, int r) { if (L <= l && r <= R) { tag[w] = tag[w] * cur_trans; mat[w] = mat[w] * cur_trans; } else { push_down(w); int mid = l + r + 1 >> 1; if (L < mid) Modify(ch[w][0],l,mid-1); if (mid <= R) Modify(ch[w][1],mid,r); maintain(w); } } inline void modify(int l, int r, int delta) { L = l; R = r; cur_trans = trans ^ delta; Modify(root,1,n); } void query(int w, int l, int r) { if (L <= l && r <= R) { ans_tmp += mat[w].a[1][1]; ans_tmp %= MOD; } else { push_down(w); int mid = l + r + 1 >> 1; if (L < mid) query(ch[w][0],l,mid-1); if (mid <= R) query(ch[w][1],mid,r); maintain(w); } } inline int query(int l, int r){ L = l; R = r; ans_tmp = 0; query(root,1,n); return ans_tmp; } }; int main(){ n = read(); m = read(); for (int i=1;i<=n;i++) { arr[i] = read(); } trans.a[1][2] = trans.a[2][1] = trans.a[2][2] = 1; SEG::Build(SEG::root,1,n); for (int i=1,ty,a,b,c;i<=m;i++) { ty = read(); a = read(); b = read(); if (ty == 1) { SEG::modify(a,b,read()); } else { printf("%d\n",SEG::query(a,b)); } } return 0; }
好文章!666,学习了
We are a bunch of volunteers and opening a brand new scheme in our community.
Your web site offered us with useful info to work
on. You have done a formidable job and our whole community will likely
be grateful to you.
I pay a quick visit each day a few blogs and information sites to read
articles, except this website gives feature based content.
I will immediately clutch your rss as I can’t find your e-mail subscription hyperlink or newsletter service.
Do you have any? Please let me realize so that I could
subscribe. Thanks.
What’s up, yup this paragraph is in fact nice and I have learned lot of things from it regarding blogging.
thanks.
Whats up are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to get started
and set up my own. Do you need any coding knowledge to make your own blog?
Any help would be really appreciated!
It’s going to be end of mine day, however before ending I am reading this enormous piece of writing to increase my experience.
You’re so cool! I do not suppose I’ve read a single thing like that before.
So wonderful to discover somebody with a few original thoughts on this topic.
Really.. many thanks for starting this up. This website is one thing that is required on the internet, someone with some originality!
Very shortly this web site will be famous amid all blog people, due
to it’s pleasant posts
My family members always say that I am killing my time here at web, but I know I am getting
knowledge everyday by reading thes nice content.
Hi to all, since I am actually keen of reading this webpage’s post to be updated daily.
It carries nice material.
Very soon this web page will be famous amid all blog users, due to it’s good
content
Have you ever thought about including a little bit more than just your articles?
I mean, what you say is fundamental and all. But just imagine if you added some great graphics or videos to
give your posts more, “pop”! Your content is excellent but with pics and video clips, this blog could certainly be one of the very
best in its niche. Good blog!
certainly like your web site however you have to take a
look at the spelling on quite a few of your posts.
Several of them are rife with spelling problems and I in finding it
very troublesome to inform the reality nevertheless I will surely come again again.
This is a topic that is close to my heart… Best wishes!
Where are your contact details though?
Its not my first time to pay a quick visit this web
page, i am browsing this site dailly and obtain nice information from here everyday.
I am no longer positive the place you’re getting
your information, however great topic. I must spend some time studying more
or working out more. Thank you for fantastic information I was
searching for this information for my mission.
Hi are using WordPress for your site platform? I’m new to the
blog world but I’m trying to get started and create
my own. Do you require any html coding knowledge to make your own blog?
Any help would be greatly appreciated!
Wow, marvelous blog structure! How lengthy have you been blogging for?
you make running a blog look easy. The total glance of your website
is great, let alone the content material!
Hi there! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard
on. Any tips?
Thanks for any other informative website. Where else may I get that
type of info written in such an ideal method? I’ve a
challenge that I’m just now working on, and I’ve been at the look out for
such information.
Way cool! Some extremely valid points! I appreciate you writing this post and the rest of the site is also very good.
Excellent post. I was checking constantly this blog and I am
impressed! Extremely useful information specifically the last part
🙂 I care for such information a lot. I was seeking this certain info for a
long time. Thank you and good luck.
Thank you, I have just been searching for information approximately this subject for ages and
yours is the best I’ve discovered till now.
But, what in regards to the conclusion? Are you sure in regards to
the source?
Right here is the right website for everyone who hopes to find out about this topic.
You know so much its almost hard to argue with you (not that
I personally would want to…HaHa). You definitely put a fresh spin on a subject that has been written about for decades.
Excellent stuff, just excellent!
My brother recommended I would possibly like this web site.
He was once totally right. This post actually made my day.
You can not imagine just how a lot time I had spent for this information! Thanks!
plenty of fish natalielise
Inspiring story there. What happened after? Take care!
I am no longer positive the place you’re getting your info, however great
topic. I needs to spend a while finding out more or
understanding more. Thanks for fantastic information I used to
be in search of this info for my mission.
Truly no matter if someone doesn’t know then its up to other visitors that they
will help, so here it occurs.
I have read so many posts about the blogger lovers however this
piece of writing is truly a fastidious article, keep it up.
pof natalielise
Can you tell us more about this? I’d like to find out more details.
Thank you, I’ve just been looking for information approximately
this topic for a long time and yours is the best I’ve found out till
now. However, what about the bottom line? Are you positive about the source?
plenty of fish natalielise
Hi there to every body, it’s my first pay a quick visit of this webpage; this
webpage consists of awesome and in fact good information for readers.
Now I am ready to do my breakfast, later than having my breakfast coming
yet again to read more news.
We are a bunch of volunteers and opening a brand new scheme in our community.
Your site provided us with helpful information to work on. You have performed a formidable task and our
entire group might be grateful to you.
I am regular reader, how are you everybody? This article posted at this website is genuinely good.
Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point. You clearly know what youre talking about, why throw away your intelligence
on just posting videos to your blog when you could be giving us something
informative to read?
I do not even know how I ended up here, but I thought this post was good.
I don’t know who you are but certainly you are going to a famous blogger if you are not
already 😉 Cheers!
I love looking through an article that will make
men and women think. Also, thanks for allowing
me to comment!
I all the time used to study post in news papers but now as
I am a user of internet thus from now I am using net for posts, thanks to web.
What’s up, I want to subscribe for this website to get
latest updates, so where can i do it please help.
Howdy! Would you mind if I share your blog with my facebook group?
There’s a lot of people that I think would really appreciate your content.
Please let me know. Thanks
You really make it seem so easy along with your presentation but I find
this matter to be actually something which I believe I’d by no
means understand. It seems too complicated and extremely vast for me.
I’m having a look forward for your subsequent post, I’ll
attempt to get the hang of it!
Its like you read my mind! You seem to know a lot about this, like you wrote the book
in it or something. I think that you can do
with a few pics to drive the message home a bit, but instead of
that, this is magnificent blog. A great read. I will definitely be back.
What a information of un-ambiguity and preserveness of precious knowledge concerning
unpredicted emotions.
It’s going to be end of mine day, however before ending I am reading
this wonderful piece of writing to improve my know-how.
My family all the time say that I am killing
my time here at net, however I know I am getting knowledge
every day by reading thes good articles or reviews.
Heya i am for the first time here. I came across this board and I find It truly useful & it helped me out a lot.
I hope to give something back and aid others like you helped
me.
It’s not my first time to go to see this site, i am
visiting this site dailly and get good facts from here all the time.
Having read this I thought it was rather informative. I appreciate you spending some time
and effort to put this short article together. I once again find myself
spending a significant amount of time both reading and leaving comments.
But so what, it was still worthwhile!
I blog often and I genuinely thank you for your content.
This article has truly peaked my interest. I am going to take a note of
your blog and keep checking for new details about once per week.
I opted in for your RSS feed too.
Link exchange is nothing else however it is only placing the other person’s webpage link on your page at appropriate
place and other person will also do similar in support
of you.
Hello! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?
I was suggested this web site by my cousin. I am not sure whether this post is written by him as
nobody else know such detailed about my problem.
You are amazing! Thanks!
I was curious if you ever thought of changing the page layout
of your website? Its very well written; I love what youve
got to say. But maybe you could a little more in the way of content so people could connect
with it better. Youve got an awful lot of text for only having 1 or 2 pictures.
Maybe you could space it out better?
Heya i am for the first time here. I came across this
board and I find It really useful & it helped me out much.
I hope to give something back and aid others like you aided me.
When someone writes an piece of writing he/she keeps the idea of a user in his/her mind that how a user can understand it.
So that’s why this piece of writing is perfect.
Thanks!
It’s genuinely very difficult in this active life to listen news on Television, thus I just use world wide web for that reason, and
take the hottest information.
My partner and I absolutely love your blog and find many of your post’s to be precisely what I’m looking for.
Does one offer guest writers to write content to suit your needs?
I wouldn’t mind writing a post or elaborating on some of the subjects you write with regards to here.
Again, awesome site!
Hey! Quick question that’s completely off topic.
Do you know how to make your site mobile friendly?
My web site looks weird when browsing from my iphone 4.
I’m trying to find a template or plugin that
might be able to resolve this issue. If you have any suggestions, please share.
Thanks!
Wow that was odd. I just wrote an extremely long comment but after
I clicked submit my comment didn’t show up. Grrrr…
well I’m not writing all that over again. Anyways, just wanted to
say great blog!
Hello there! This article couldn’t be written much better!
Looking through this post reminds me of my previous roommate!
He constantly kept preaching about this. I’ll forward this information to him.
Pretty sure he’s going to have a good read. Many thanks for sharing!
Why viewers still use to read news papers when in this technological globe the whole thing is available on web?
This is a topic which is close to my heart… Many thanks!
Where are your contact details though?
Hey there! I know this is somewhat off topic but I was wondering which blog platform are you using for this website?
I’m getting fed up of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.
I would be awesome if you could point me in the direction of a good platform.
Great information. Lucky me I found your website by accident
(stumbleupon). I’ve saved as a favorite for later!
I every time used to study post in news papers but now as I am
a user of net therefore from now I am using net for content, thanks to web.
It’s really very complicated in this full of activity life to listen news on TV, so I just use world wide web for that reason, and obtain the hottest information.
Hello, always i used to check blog posts here in the early hours in the break of day, for the reason that i enjoy to find out
more and more.
Hello! Do you know if they make any plugins to protect
against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
I discovered your weblog site on google and test a few of your early posts. Proceed to keep up the excellent operate. I just extra up your RSS feed to my MSN Information Reader. Seeking ahead to reading extra from you afterward!…
Its not my first time to pay a quick visit this web page, i am
browsing this site dailly and obtain nice facts from here everyday.
This web site certainly has all the information I needed concerning this subject and didn’t know who to ask.
Wow, amazing blog format! How lengthy have you been running a blog for?
you made blogging glance easy. The overall look of your
web site is magnificent, as well as the content!
Hello! I’ve been reading your weblog for a long time
now and finally got the bravery to go ahead and give you a shout out from Austin Texas!
Just wanted to mention keep up the fantastic job!
First of all I would like to say awesome blog! I had a quick question in which I’d
like to ask if you don’t mind. I was curious to find
out how you center yourself and clear your thoughts prior to writing.
I’ve had trouble clearing my thoughts in getting my ideas out.
I do enjoy writing but it just seems like the first 10 to 15
minutes tend to be lost simply just trying to figure out how to
begin. Any recommendations or tips? Many thanks!
Now I am ready to do my breakfast, when having my breakfast coming over
again to read more news.
I quite like reading through a post that can make men and women think.
Also, thank you for allowing me to comment!
Hey there! Would you mind if I share your
blog with my facebook group? There’s a lot of people that I think would really
appreciate your content. Please let me know. Cheers
Can I just say what a relief to discover a person that
genuinely understands what they are talking about online.
You definitely understand how to bring a problem to light and make it important.
More people really need to look at this and understand this side of your
story. I can’t believe you’re not more popular because you
certainly have the gift.
I like what you guys are up too. Such smart work and reporting! Carry on the excellent works guys I have incorporated you guys to my blogroll. I think it will improve the value of my website 🙂