记录编号	320851	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.155 s
提交时间	2016-10-12 21:08:50	内存使用	0.30 MiB

#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <cmath>
using namespace std;
int fast_read()
{
    int r;
    char c;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}

#define MOD 998244353
#define MAXN 10002
#define OVERF(x) if(x >= MOD)x -= MOD;
int lazy1[122];
int lazy2[123];
int moni[MAXN];
int fib[10002];
int magic;
void pre(int n)
{
    fib[0] = 0;
    fib[1] = fib[2] = 1;
    for(int i = 3; i <= n; i++)
    {
        fib[i] = fib[i-1]+fib[i-2];
        OVERF(fib[i]);   //%
    }
}
void add(int l, int r)
{
    int k = 1;
    for(int i = l; i <= r;)
    {
        if(i % magic == 0 && i + magic - 1 <= r)
        {
            int p = i/magic;
            lazy1[p] += fib[k];
            OVERF(lazy1[p]);
            lazy2[p] += fib[k+1];
            OVERF(lazy2[p]);
            
            i += magic;
            k += magic;
        }else
        {
            moni[i] += fib[k];
            OVERF(moni[i]);
            k++;
            i++;
        }
    }
}
int query(int p)
{
    int b = p/magic;
    int a1 = lazy1[b], a2 = lazy2[b];
    if(p == b*magic)return (a1+moni[p])%MOD;
    if(p == b*magic+1)return (a2+moni[p])%MOD;
    int t;
    for(int i = b*magic+2; i <= p; i++)
    {
        t = a1+a2;
        OVERF(t);
        
        a1 = a2;
        a2 = t;
    }
    return (t+moni[p])%MOD;
}
int main()
{
    freopen("chenyao_fib_game.in", "r", stdin);
    freopen("chenyao_fib_game.out", "w", stdout);
    int n, m;
    n = fast_read();
    m = fast_read();
    magic = (int)sqrt(n);
    if(magic < 2)magic = 2;
    pre(n);
    while(m--)
    {
        int op = fast_read();
        if(op)
        {
            int a = fast_read();
            int b = fast_read();
            add(a, b);
        }else
        {
            int p = fast_read();
            printf("%d\n", query(p));
        }
    }
    return 0;
}