Contest1337/e.c

#include <stdio.h>
#define MOD 998244353

int dp[500005];

void init()
{
    int i;
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for (i = 0; i < 500000; i ++)
    {
        dp[i+1] = (dp[i] + dp[i+1]) % MOD;
        dp[i+2] = (dp[i] + dp[i+2]) % MOD;
        dp[i+3] = (dp[i] + dp[i+3]) % MOD;
    }
}

int main()
{
    init();
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}