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

#include<cstdio>
#include<cstring>
using namespace std;
const int p=998244353,N=100010;
typedef long long ll;
struct matrix{
	ll a[2][2];
	matrix(ll x=0,ll y=0,ll z=0,ll w=0){
		a[0][0]=x;a[0][1]=y;
		a[1][0]=z;a[1][1]=w;
	}
	matrix operator * (const matrix &x){
		matrix ans;
		for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
		for (int k=0;k<2;k++)
			ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j])%p;
		return ans;
	}
}x(0,1,1,1),f[N];
inline ll val(ll f1,ll f2,int p){
	matrix ans(f1,f2,f1,f2);
	if (p>1) ans=ans*f[p-1];
	return ans.a[0][0];
}
int n,m;ll F[N][2];
#define lc x<<1
#define rc (x<<1)|1
void update(int x,int l,int r){
	if (l!=r){
		int mid=(l+r)>>1;
		F[lc][0]=(F[lc][0]+F[x][0])%p;
		F[lc][1]=(F[lc][1]+F[x][1])%p;
		F[rc][0]=(F[rc][0]+val(F[x][0],F[x][1],mid+2-l))%p;
		F[rc][1]=(F[rc][1]+val(F[x][0],F[x][1],mid+3-l))%p;
		F[x][0]=F[x][1]=0;
	}
}
//在区间[L,R]上加上首末项分别为f1,f2的fib 
void change(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R){
		F[x][0]=(F[x][0]+val(1,1,l-L+1))%p;
		F[x][1]=(F[x][1]+val(1,1,l-L+2))%p;
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid) change(lc,l,mid,L,R);
	if (R>mid) change(rc,mid+1,r,L,R);
}
ll getnum(int x,int l,int r,int p){
	update(x,l,r);
	if (l==r) return F[x][0];
	int mid=(l+r)>>1;
	if (p>mid) return getnum(rc,mid+1,r,p);
		else return getnum(lc,l,mid,p); 
}
int main()
{
	freopen("chenyao_fib_game.in","r",stdin);
	freopen("chenyao_fib_game.out","w",stdout);
	scanf("%d%d",&n,&m);
	f[1]=x;for (int i=2;i<=n;i++) f[i]=f[i-1]*x;
	while (m--){
		int ch,l,r,p;
		scanf("%d",&ch);
		if (!ch){
			scanf("%d",&p);
			printf("%lld\n",getnum(1,1,n,p));
		}
		else{
			scanf("%d%d",&l,&r);
			change(1,1,n,l,r);
		}
	}
	return 0;
}