#P1118. 活动分组

活动分组

题目描述

现在小核桃所在的班级正在进行活动的分组。其中有一个小组将被设置为特殊小组。

测验时,第i个学生会有一个心理预期num[i]num[i]。当下列任意一个条件被满足时,这个学生不会感到不平衡。

  • 如果这名学生被分进特殊小组,且总共分进小组的人 严格大于 num[i]num[i]
  • 如果这名学生没有被分进特殊小组,且总共分进小组的人 严格小于 num[i]num[i]

现在要求你合理分组,使得所有学生都不会感到不平衡。

你的任务是计算总共有多少种分组的方法。

提醒:特殊小组可以没有任何成员,也可以全员都在特殊小组中。

输入格式

第一行一个正整数nn,表示一共有多少学生。

接下来一行nn个正整数,依次表示每个学生的心理预期。

输出格式

输出一个整数,表示总共有多少种分组的方法。

8
6 0 3 3 6 7 2 7
3

样例解释

方案1:选[0],特殊小组共一个学生。

方案2:选[0, 3, 3, 2],特殊小组共4个学生。

方案3:选全体学生。

数据规模与约定

每组数据点10分,共10组数据。

对全体数据有心理预期0num[i]<n0\leq num[i]<n

数据点编号 n的范围 卡片数值范围
#1~#3 1n101\le n\le 10
#4~#5 1n1,0001\le n\le 1,000 各学生心理预期分别为 0,1,2,3,...,n10,1,2,3,...,n-1
#6~#7
#9~#10 1n100,0001\le n\le 100,000

大样例

大样例下载