5372: Cycle Binary
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
We can rewrite a binary string (i.e. strings where only 0 or 1 is included) s as kp+p′. p′ is a prefix of p (p′ could be empty). +p′ means concatenating p′ to the last of kp. kp means concatenating k copies of p, where p is the unit of s.
The unit of a binary string s is when ignoring p′, the non-empty string p which makes k maximal.
We define v(s) as the value of s, which is k in the previous statement. For example, v(01001001)=2, because 01001001 could be written as 2(010)+(01), and v(11111)=5 since 11111 could be written as 5(1) and p′ is empty .
Now given n, your task is to calculate the sum of the value of all binary strings whose length is exactly n. As the answer could be very large, just output the answer modulo 998244353.
The unit of a binary string s is when ignoring p′, the non-empty string p which makes k maximal.
We define v(s) as the value of s, which is k in the previous statement. For example, v(01001001)=2, because 01001001 could be written as 2(010)+(01), and v(11111)=5 since 11111 could be written as 5(1) and p′ is empty .
Now given n, your task is to calculate the sum of the value of all binary strings whose length is exactly n. As the answer could be very large, just output the answer modulo 998244353.
输入
The first line contains a single positive integer T (1≤T≤100), indicating that there are T test cases.
Each test case contains a single positive integer n (1≤n≤109) in one line.
It is guaranteed that ∑n≤1010.
Each test case contains a single positive integer n (1≤n≤109) in one line.
It is guaranteed that ∑n≤1010.
输出
For each test case, print an integer indicating the answer modulo 998244353 in a single line.
样例输入 复制
5
1
2
3
114
514样例输出 复制
2
6
12
954037435
530871613提示
For n=3,
v(000)+v(001)+v(010)+v(011)+v(100)+v(101)+v(110)+v(111)
=3+1+1+1+1+1+1+3
=12
v(000)+v(001)+v(010)+v(011)+v(100)+v(101)+v(110)+v(111)
=3+1+1+1+1+1+1+3
=12