问题1518--小P的战斗

1518: 小P的战斗

时间限制: 1 Sec  内存限制: 512 MB
提交: 30  解决: 6
[提交] [状态] [讨论版] [命题人:]
题目描述
小P非常喜爱军事,今天他要指挥一场战斗:
有n+1个士兵,其中每一个兵属于第Si个兵种(Si≤n),每个兵种至少有一个兵 (即只有一个兵种有两个兵)
现在小P从前到后检阅每个兵,在检阅每一个兵时,他都可以选择是否把这个兵加入当前作战队列的队尾。
对于长度为L的作战队列,问有多少种组合方式(如果两个队列中相同位置兵种相同,则只算一种) ,结果对109+7取模 
输入
第一行一个正整数n,表示有n种兵种。
第二行n+1个正整数S1……Sn+1,描述每个士兵的兵种。
输出
n+1行,对于第 i 行,输出一个整数表示可组成长度为 i 的不同队列的数量,答案对109+7取模。
样例输入 Copy
3
1 2 1 3
样例输出 Copy
3
5
4
1
提示
样例解释
长度为1的作战队列有3个:1,2,3。
长度为2的作战队列有5个:11,12,13,21,23。
长度为3的作战队列有4个:121,123,113,213。
长度为4的作战队列有1个:1213。


对于20%的数据,n≤20。
对于40%的数据,n≤2000。
对于100%的数据,n≤100000,1≤ai≤n。


来源/分类