记录编号	322333	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.466 s
提交时间	2016-10-15 06:11:42	内存使用	0.44 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10005,INF=998244353;
int n,m,size,F[maxn],clo[maxn],f[maxn],c[maxn];
void _in(){
	F[1]=1;scanf("%d%d",&n,&m);int i;
	for(i=2;i<=n;i++)F[i]=(F[i-1]+F[i-2])%INF;
	size=(int)sqrt(n+0.0);
	for(i=1;i<=n;i++)clo[i]=(i-1)/size+1;
}
void _add(int s,int t){
	int l=clo[s],r=clo[t],i,j;
	if(l==r){
		for(i=s;i<=t;i++)c[i]+=F[i-s+1],c[i]%=INF;
		return;
	}
	for(i=s;clo[i]==l;i++)c[i]+=F[i-s+1],c[i]%=INF;
	for(i=t;clo[i]==r;i--)c[i]+=F[i-s+1],c[i]%=INF;
	for(i=l+1;i<r;i++){
		j=size*(i-1)+1;
		f[j]+=F[j-s+1],f[j]%=INF;
		j++;
		f[j]+=F[j-s+1],f[j]%=INF;	
	}
}
int _get(int pos){
	int tmp=size*(clo[pos]-1)+1,cur=tmp+1;
	if(pos==tmp)return f[pos]+c[pos];
	while(cur^pos)
		f[cur+1]=(f[cur]+f[tmp])%INF,
		cur++,tmp++;
	return f[pos]+c[pos];
}
void _work(){
	_in();int ope,l,r,x;
	while(m--){
		scanf("%d",&ope);
		if(ope)scanf("%d%d",&l,&r),_add(l,r);
		else scanf("%d",&x),printf("%d\n",_get(x)%INF);
	}
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("chenyao_fib_game.in","r",stdin);
	freopen("chenyao_fib_game.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}