CF438E The Child and Binary Tree

    • 236通过
    • 349提交
  • 题目来源 CodeForces 438E
  • 评测方式 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类违反进行处理。