TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3236
  • 题目
  • P3236多项式求复合逆(大朋友和多叉树)
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 2s
    问题描述

    我们的大朋友很喜欢计算机科学,而且尤其喜欢多叉树。对于一棵带有正整数点权的有根多叉树,如果它满足这样的性质,我们的大朋友就会将其称作神犇的:点权为1的结点是叶子结点;对于任一点权大于1的结点u,u的孩子数目deg[u]属于集合D,且u的点权等于这些孩子结点的点权之和。
    给出一个整数s,你能求出根节点权值为s的神犇多叉树的个数吗?请参照样例以更好的理解什么样的两棵多叉树会被视为不同的。
    我们只需要知道答案关于950009857(453*221+1,一个质数)取模后的值。

    输入格式

    第一行有2个整数s,m。
    第二行有m个互异的整数,d[1],d[2],…,d[m],为集合D中的元素。

    输出格式

    输出一行仅一个整数,表示答案模950009857的值。

    样例输入

    4 2
    2 3 

    样例输出

    10

    提示

    样例解释:


    数据范围:
    1<=m<s<=105
    2<=d[i]<=s