【Codeforces 718C】Sasha and Array

题目传送门: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;
}

81 thoughts to “【Codeforces 718C】Sasha and Array”

  1. 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.

  2. 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!

  3. 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!

  4. 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!

  5. 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.

  6. 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.

  7. 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!

  8. 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!

  9. 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?

  10. 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.

  11. 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.

  12. 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!

  13. 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

  14. 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.

  15. 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.

  16. 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?

  17. 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!

  18. 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!

  19. 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!

  20. 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.

  21. 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.

  22. 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?

  23. 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!

  24. 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.

  25. 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!

  26. 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!

  27. 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!

  28. 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.

  29. 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.

  30. 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!…

  31. 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!

  32. 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!

  33. 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

  34. 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.

  35. 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 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *