记录编号	321024	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	1.294 s
提交时间	2016-10-13 08:09:33	内存使用	0.44 MiB

#include <cstdio>
#include <cmath>
typedef int Utype;
const Utype MAXN=10010;
const Utype MOD=998244353;
Utype fib[MAXN],w[MAXN];
Utype lb[MAXN],lc[MAXN];
Utype block;
void prepare(int N) 
{
	fib[0]=1;
	fib[1]=0;
	fib[2]=fib[3]=1;
	for(Utype i=4;i<=N+1;++i)
		fib[i]=(fib[i-1]+fib[i-2])%MOD;
}
void change(int l,int r)
{
	for(Utype i=l,j=2;i<r;++i,++j){
		if(i%block==0&&i+block<r){
			lb[i/block]=(lb[i/block]+fib[j-1])%MOD;
			lc[i/block]=(lc[i/block]+fib[j-2])%MOD;
			j+=block-1;i+=block-1;
		}else {
			w[i]=(w[i]+fib[j])%MOD;
		}
	}
}
Utype ask(Utype pos)
{
	Utype a=lb[pos/block],b=lc[pos/block],c;
	for(Utype i=(pos/block)*block;i<=pos;++i){
		c=a;a=(a+b)%MOD;b=c;
	}return (a+w[pos])%MOD;
}
int main(){
	freopen("chenyao_fib_game.in","r",stdin);
	freopen("chenyao_fib_game.out","w",stdout);
	Utype N,M,a,b;
	scanf("%d%d",&N,&M);
	prepare(N);block=sqrt(N);
	for(Utype i=1;i<=M;++i){
		scanf("%d",&a);
		switch(a){
			case 0:
				scanf("%d",&b);
				printf("%d\n",ask(b-1));
				break;
			default :
				scanf("%d%d",&a,&b);
				change((a-1),b);
				break;
		}
	}fclose(stdin);fclose(stdout);
	return 0;
}