Announcement 1: the output format has changed
A term is an inductively defined structure, which is either an integer constant, or of the form (S♯T) where S,T are terms and ♯ is a binary operator. Two terms are equal if and only if either they are the same constant, or if both or them are of the form (S1♯1T1) and (S2♯2T2), and S1=S2,T1=T2 and ♯1,♯2 are the same binary operator. Some examples are (1+(2∗3)),0,(42∨11).
We have N distinct non-commutative, non-associative* binary operators ⋈i,1≤i≤n, and they have the property that the time taken to process the term (S⋈iT),cost((S⋈iT))=C(⋈i)+cost(S)+cost(T), where the operation cost C(⋈i) depends only on the operator and not on the values of S,T, and the cost of a constant is 0. We are interested in finding the number of terms we can compute within a certain amount of time T.
Given N operators with associated costs C(⋈1),C(⋈2),...,C(⋈n), find the number of terms (formed by operators and 1s) which take time t to be computed for all integers t such that 1≤t≤T.**
Since the numbers could be very large, find the answers modulo M=998244353.
Constraints: 1≤N≤105,1≤T≤105,1≤C(⋈i)≤105
Input format:
First line contains two integers N,T (the number of operators and the time limit to compute the terms)
The second line contains N space separated distinct integers C(⋈i), for 1≤i≤n.
Output format:
In T separate lines, print T space separated integers, such that the ith of them is the number of terms that take time i to be evaluated, modulo M.
Problem author: Navneel Singhal
Footnotes:
*Note that this is in general not needed, because the terms ((1+1)+1)and(1+(1+1)) are syntactically different, but this is just to ensure there is no confusion.
**This means that we are looking at terms like 1 and ((1/(1−1))∧1) but not (2%3) and 5
Sample test:
For N=1,C(⋈1)=1,T=3, we have the following output:
125
This is because (replacing ⋈1 with the more convenient symbol +) the only term with cost 1 is (1+1), the only terms with cost 2 are (1+(1+1))and((1+1)+1), and the only terms with cost 3 are ((1+1)+(1+1)),(1+(1+(1+1))),(1+((1+1)+1)),((1+(1+1))+1),(((1+1)+1)+1).