3172:特殊的01串

时间限制:2 S   /  内存限制:65536 KB
AC:42   /  Submit:140
问题描述

我们定义一个字符串是特殊的01串:

1.空串是特殊的01串。
2.仅由字符 0 和 1 构成且任意两个相邻的字符不都为 1。

现在请你构造一个长度为 n 的特殊的01串,请问你可以构造多少个?

输入描述

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1e5)

每组案例是一个整数 n,代表构造字符串的长度。(0 <= n <= 1e6)

输出描述

针对每组案例,输出你可以构造多少个,然后换行。

由于答案可能很大,所以你只需要输出它对 998244353 取模以后的结果。

样例输入复制样例

1
3

样例输出

5

提示说明

长度为 3 的特殊的01串可以是 100 010 001 101 000。

相关

20-21(2)第0次线上赛


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1