UOJ Logo

NOI.AC

1S 512MB

#45. count

Statistics

序列计数(count)

题目描述

长度为$n+1$的序列$A$,其中的每个数都是不大于$n$的正整数,且$n$以内每个正整数至少出现一次。

对于每一个正整数$k=1,..,n+1$,求出的本质不同的长度为$k$的子序列(不一定要连续)的数量。对$10^9+7$取模。

输入格式

第一行一个正整数$n$。

第二行$n+1$个正整数$A_{1}..A_{n+1}$,描述序列$A$。

输出格式

$n+1$行,对于第$i$行,输出一个整数表示长度为$i$的本质不同子序列的数量,对$10^9+7$取模。

样例

input1

3
1 2 1 3

output1

3
5
4
1

explanation

长度为$1$的子序列有$3$个:$1$ ,$2$ ,$3$。

长度为$2$的子序列有$5$个:$11$ ,$12$ ,$13$,$21$,$23$。

长度为$3$的子序列有$4$个:$121$ ,$123$ ,$113$,$213$。

长度为$4$的子序列有$1$个:$1213$。

input2

见样例 ex_count2.in。

output2

见样例 ex_count2.out。

数据范围和约定

对于$20\%$的数据,$n\le20$。

对于$40\%$的数据,$n\le2000$。

对于额外$20\%$的数据,保证$A$中相同的数一定相邻。

对于$100\%​$的数据,$n\le100000​$,$1\le A_{i}\le n​$。

时间限制:$1s$ 空间限制:$512MB$

样例下载

样例下载