SCAU1西园

1 西园

Time Limit:1000MS Memory Limit:65535K
题型: 编程题 语言: 无限制
描述
华农人多已经不是一天两天的事了&＃xff0c;这导致学生吃饭要排很久的队。
现在&＃xff0c;传说中的Spring Brother为了让华农学生有个舒服的就餐环境&＃xff0c;斥巨资改建华山西园饭堂。
改建后的西园饭堂单单窗口&＃xff0c;厨师的数量和级别就有一个巨大的飞跃&＃xff0c;学生们吃饭再也不需要排队啦。
由于厨师数目很多&＃xff0c;为了便于管理。每个厨师会被分发一个正整数编号(所有编号都有且仅有一个厨师拥有)。
编号的数值越小&＃xff0c;代表厨师的厨艺越好&＃xff0c;当然&＃xff0c;学生们也就越喜欢吃他煮的饭菜。
然而&＃xff0c;厨师们十分懒惰&＃xff0c;他们每次只愿意提供一份饭菜&＃xff0c;所以&＃xff0c;厨师们就要一一对应地提供饭菜给学生们。

现在&＃xff0c;有n个学生需要到饭堂就餐。
学生们对饭菜有一定的要求&＃xff0c;他们心中都有一个标准的厨师编号&＃xff0c;只有编号小于等于标准编号的厨师&＃xff0c;他们才愿意选择这些厨师提供的饭菜。
现在告诉你&＃xff0c;每个学生心中标准的厨师编号。
聪明的10级同学&＃xff0c;请帮我计算下&＃xff0c;总共有多少种分配的方式&＃xff0c;使得所有学生都能选择到适合自己的厨师。


输入格式
输入第一行为整数T&＃xff0c;表示case的数目。
下面有T个case&＃xff0c;每个case的第一行为整数n(1 <&＃61; n <&＃61; 10000)&＃xff0c;表示有n个学生。
然后给出n个正整数&＃xff0c;数的大小不超过1000000&＃xff0c;代表学生们心中标准的厨师编号&＃xff0c;第一个数为第一个学生心中标准的厨师编号&＃xff0c;第二个数为第二个学生的&＃xff0c;以此类推。
数与数以空格分隔。
输出格式
输出总共有多少种分配的方式&＃xff0c;使得所有学生都能选择到适合自己的厨师。由于数目可能很大&＃xff0c;你只需将答案%1000000007&＃xff0c;再输出即可。
输入样例
3
1
5
2
5 8
3
2 1 2
输出样例
5
35
0
提示
由于n有10000&＃xff0c;所以某些天真的想法会超时&＃xff0c;请加以优化或者找更好的方法替代。
D题数据有点小bug&＃xff0c;有一组数据超出范围&＃xff0c;该数据是
2
1000000000 999999999
仅此一组&＃xff0c;若遇到这组数据&＃xff0c;直接输出正确答案即可。

#include
#include
#include
#include
using namespace std;
int a[10010];
int main()
{int T;cin>>T;while(T--){int n;long long s&＃61;1;scanf("%d",&n);for(int i&＃61;0; i<n; i&＃43;&＃43;)scanf("%d",&a[i]);sort(a,a&＃43;n);int i;for(i&＃61;0; i<n; i&＃43;&＃43;){if(a[i]-i<&＃61;0){s&＃61;0;break;}s&＃61;s*(a[i]-i)%1000000007;}if(i<n) printf("0\n");else printf("%lld\n",s);}return 0;
}