洛谷 P1866：编号 ← 排序

【题目来源】
https://blog.csdn.net/hnjzsyjyj/article/details/162212476

【题目描述】
太郎有 N 只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子 i 想要一个整数，介于 1 和 Mi 之间（可以为 1 或 Mi）。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。你只用输出答案对10^9+7取余的结果即可。如果这是不可能的，就输出 0。

【输入格式】
第一行是一个整数 N。
第二行 N 个整数 Mi。​​​​​​​

【输出格式】
一个整数，表示方案总数。​​​​​​​

【输入样例】
2
5 8

【输出样例】
35

【数据范围】
对于全部数据，1≤N≤50，1≤Mi≤1000。

【算法分析】
设已将所有兔子的编号上限升序排序。分配到第 i 只兔子时，前 i-1 只兔子已经占用了 i-1 个互不重复的数字，而该兔子仅能选取 1~v[i] 内的数，因此合法可选编号的数量为 v[i]-(i-1)，记作 cnt = v[i] - (i-1)。

【算法代码】

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MOD=1e9+7; const int N=55; int v[N]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { cin>>v[i]; } sort(v+1,v+1+n); LL ans=1; for(int i=1; i<=n; i++) { int cnt=v[i]-(i-1); if(cnt<=0) { ans=0; break; } ans=ans*cnt%MOD; } cout<<ans<<endl; return 0; } /* in: 2 5 8 out: 35 */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/162212476