#P3684. 大朋友和多叉树

    ID: 2885 传统题 4000ms 512MiB 尝试: 579 已通过: 231 难度: 9 上传者: 标签>CF2600省选/NOI-普通生成函数Lagrange 反演多项式对数多项式指数多项式求逆多项式牛顿迭代导数积分转化截断幂级数NTT拉格朗日反演

大朋友和多叉树

题目描述

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

输入格式

第一行有 22 个整数 s,ms,m。 第二行有 mm 个互异的整数,d1,d2,⋯ .dmd_1,d_2,\cdots.d_m,为集合 DD 中的元素。

输出格式

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

4 2
2 3
10

img

数据规模与约定

1≤m<s≤105,2≤di≤s1\le m<s\le 10^5, 2\le d_i\le s,有 33 组小数据和 33 组大数据。

题目来源

By Jcvb