牛客NOIP暑期七天营-普及组4-A火龙果树

题目大意：一棵树，第一年只有祖先0；每一年，0可以分支出1个1，0可以分支出1个0和1个1，n年后共有多少个结点？

f[i][j]表示第i年数字j的数量：

f[i][0] = f[i-1][1]，因为只有1能得到0；

f[i][1] = f[i-1][0]+f[i-1][1]，因为0和1都能够得到1。

询问比较多，要预处理出10000000以内的所有答案，O(1)回答询问。

只有加法，用减法代替取模，同时避免开long long爆空间。

#include <stdio.h>
#define N 10000005
#define mo 998244353
int t, n, m, i, j, k, f[N][2], s[N];
int main(){
    f[1][0] = f[2][1] = 1;
    s[1] = 1, s[2] = 2;
    for(i=3; i<N; i++){
        f[i][0] = f[i-1][1];
        f[i][1] = f[i-1][0] + f[i-1][1];
        if(f[i][1] >= mo) f[i][1] -= mo;
    }
    for(i=3; i<N; i++){
        s[i] = s[i-1] + f[i+1][1];
        if(s[i] >= mo) s[i] -= mo;
    }
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }
    return 0;
}

压缩空间：

#include <stdio.h>
#define N 10000005
#define mo 998244353
int t, n, m, i, j, k, a, b, pa, pb, s[N];
int main(){
    pa = 0, pb = s[1] = 1;
    for(i=3; i<N; i++){
        a = pb, b = pa + pb;
        if(b >= mo) b -= mo;
        s[i-1] = s[i-2] + b;
        if(s[i-1] >= mo) s[i-1] -= mo;
        pa = a, pb = b;
    }
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }
    return 0;
}