Computational cost

0

0 votes
Problem

Announcement 1: the output format has changed

A term is an inductively defined structure, which is either an integer constant, or of the form (ST) 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 (S11T1) and (S22T2), and S1=S2,T1=T2 and 1,2 are the same binary operator. Some examples are (1+(23)),0,(4211).

We have N distinct non-commutative, non-associative* binary operators i,1in, and they have the property that the time taken to process the term (SiT),cost((SiT))=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 1tT.**

Since the numbers could be very large, find the answers modulo M=998244353.

Constraints: 1N105,1T105,1C(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 1in.

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/(11))1) but not (2%3) and 5

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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).

Editor Image

?