摘要：太郎有N只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子i想要一个整数，介于1和Maxnumber[i]之间（包括1和Maxnumber[i]）。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。你只用输出答案mod 1000000007即可。如果这是不可能的，就输出0。
其实看到这个题，我第一时间想到的是深搜，不过有这句“输出答案mod 1000000007即可”就基本确定不是深搜了。
于是我就换个思路想了想：
第一次我们选择第一个序列的某一个，第二次选择就减少了一次选择机会，只能选择除了选过的以外的了，第三次选择又少了一次，第四次又少了一次......
那么不难想到：第一个*第二个-1*第三个-2*第四个-3......
这样我们稍微画画图就可以得出公式：ans*=(m[i]-sum);
sum是每次应该减少的次数（每次++），m[i]是目前的这个序列一共有多少个数。
代码如下：
#include<iostream> #include<cstdio> using namespace std; unsigned long long n,m[10010],ans=1,sum=0; int main(){ scanf("%u",&n); for(int i=0;i<n;i++){ scanf("%u",&m[i]); } for(int i=0;i<n;i++){//遍历一遍 ans*=(m[i]-sum)%1000000007;//公式 sum++;//减少的次数 } printf("%u\n",ans); return 0; }
但是这样我们会发现，当碰到5 1 2 3 2 1这样的数的时候就会over(因为2<那时候的sum，就会得到一个负数)。
那要不我们加个特判：if（m [i]>=sum）的时候才让他执行上面的那个语句？
#include<iostream> #include<cstdio> using namespace std; unsigned long long n,m[1010],ans=1,sum=0; int main(){ scanf("%u",&n); for(int i=0;i<n;i++){ scanf("%u",&m[i]); } for(int i=0;i<n;i++){//遍历 if(m[i]>=sum){//特判，如果m[i]>=sum才能执行下面的语句。 ans*=(m[i]-sum); } else{//否则就直接让ans=0 ans=0; break; } ans%=1000000007; sum++;//减少的次数 } printf("%u\n",ans); return 0; }
可是碰到5 4 5 6 2 1就又难办了（因为这样虽然会得到负数，但是还是会有很多种选编号方法的）。
那该怎么办？？
我们的救星来了！他就是——sort，只要用sort排一边序就好了。
如果不排序，我们就不知道前一个选择的号码是不是在现在这个m[i]里面，就会发生前面的情况。
AC代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; unsigned long long n,m[1010],ans=1,sum=0;//开大点总没坏处 int main(){ scanf("%u",&n); for(int i=0;i<n;i++){ scanf("%u",&m[i]); } sort(m,m+n);//排序一遍，如果不排序，我们就不知道前一个选择的号码是不是在现在这个m[i]里面，就会发生前面的情况。 for(int i=0;i<n;i++){ ans*=(m[i]-sum); ans%=1000000007;//千万不要忘了这个，如果数大了，不加这个就会over sum++; } printf("%u\n",ans); return 0; }