#1879. S>a<M

    ID: 1879 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1855来源:qoj.ac数据:公开样例枚举动态规划组合数学

S>a<M

S>a<M

题目描述

标题: S>a<M - Problem - QOJ.ac

#9637. S>a<M

Statistics

The problem was used in the following contests:

题目描述

对于大小不超过 n,且每个元素都是 [0,n] 中的整数的可重集合 S,定义一次操作 SaM(Select and Mex)为:

  1. 取出任意一个非空可重子集 T。
  2. 计算 x=mexT。
  3. 将 T 从 S 中删除后,再将 x 加入 S。

对于 S,令 f(S) 表示对 S 做任意多次 SaM 操作后,S 的不同元素的个数的最大值。

SA 酱现在给你了 S 的一个子集 T,希望你求出所有满足下列要求的大小为 n 的 S 的个数。

  • T⊆S
  • 0∈S
  • f(S)=k

你只需要求出答案对 109+7 取模的余数即可。

输入格式

第一行两个整数 n 和 |T|。

若 |T|≠0,第二行 |T| 个整数表示 T 中的元素。

输出格式

对于每个 k=1,2,…,n,输出对应的答案。

样例 1

样例输入 1
3 0
样例输出 1
0 3 7

样例 2

样例输入 2
6 2
2 2
样例输出 2
0 0 0 50 30 4

样例 3

样例输入 3
12 4
2 5 5 6
样例输出 3
0 0 0 0 0 470 5530 17352 22065 4655 308 8

样例解释

S={0,1,1},{0,0,1},{0,0,0} 时,有 f(S)=2;对于其它的 S,都有 f(S)=3。

数据范围

对于所有数据,满足 2≤n≤200,0≤|T|≤n,T 中元素 ∈[0,n]∩Z。

Subtask 分值 特殊性质 1 15 |T|=n 2 15 n≤12 3 15 n≤30 4 20 n≤70 5 15 n≤120 6 20 n≤200

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 0
0 3 7

样例 2

6 2
2 2
0 0 0 50 30 4