# CF438E The Child and Binary Tree

• 236通过
• 349提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 构造 生成函数 递归
• 难度 NOI/NOI+/CTSC
• 时空限制 7000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

我们的小朋友很喜欢计算机科学，而且尤其喜欢二叉树。 考虑一个含有n个互异正整数的序列c[1],c[2],...,c[n]。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合{c[1],c[2],...,c[n]}中，我们的小朋友就会将其称作神犇的。并且他认为，一棵带点权的树的权值，是其所有顶点权值的总和。 给出一个整数m，你能对于任意的s(1<=s<=m)计算出权值为s的神犇二叉树的个数吗？请参照样例以更好的理解什么样的两棵二叉树会被视为不同的。 我们只需要知道答案关于998244353取模后的值。

输入第一行有2个整数 n,m(1<=n<=10^5; 1<=m<=10^5)。 第二行有n个用空格隔开的互异的整数 c[1],c[2],...,c[n]（1<=c[i]<=10^5)。

输出m行，每行有一个整数。第i行应当含有权值恰为i的神犇二叉树的总数。请输出答案关于$998244353$($=7\times 17\times 2^{23}+1$,一个质数)取模后的结果。

感谢@Ez3real 提供的翻译

## 题目描述

Our child likes computer science very much, especially he likes binary trees.

Consider the sequence of $n$ distinct positive integers: $c_{1},c_{2},...,c_{n}$ . The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$ , the weight of $v$ is in the set ${c_{1},c_{2},...,c_{n}}$ . Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.

Given an integer $m$ , can you for all $s$ $(1<=s<=m)$ calculate the number of good vertex-weighted rooted binary trees with weight $s$ ? Please, check the samples for better understanding what trees are considered different.

We only want to know the answer modulo $998244353$ ( $7×17×2^{23}+1$ , a prime number).

## 输入输出格式

输入格式：

The first line contains two integers $n,m$ $(1<=n<=10^{5}; 1<=m<=10^{5})$ . The second line contains $n$ space-separated pairwise distinct integers $c_{1},c_{2},...,c_{n}$ . $(1<=c_{i}<=10^{5})$ .

输出格式：

Print $m$ lines, each line containing a single integer. The $i$ -th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to $i$ . Print the answers modulo $998244353$ ( $7×17×2^{23}+1$ , a prime number).

## 输入输出样例

输入样例#1： 复制
2 3
1 2

输出样例#1： 复制
1
3
9

输入样例#2： 复制
3 10
9 4 3

输出样例#2： 复制
0
0
1
1
0
2
4
2
6
15

输入样例#3： 复制
5 10
13 10 6 4 15

输出样例#3： 复制
0
0
0
1
0
1
0
2
0
5


## 说明

In the first example, there are $9$ good vertex-weighted rooted binary trees whose weight exactly equal to $3$ :

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。