AtCoder
Leon |
12 Jul 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目描述
题目给出一个拥有N个整数的数字串C，而你要求拥有N个整数的数字串A的数量，且A要符合以下的要求： \(1\leq A_i\leq C_i(1\le i\le N)\)
\(A_i\neq A_j(1\le i<j\le N)\) （因为答案可能会很大，所以请将答案模（10^9+7））
思路
先将所有的数放进数组里面，再将数组排序，最后将每个数减去这个数在数组中的index相乘，就能得出答案。（乘法原则）。
遍历数组O（N）
排序数组O（NlogN）
所以总体复杂度是O（NlogN）
代码实现
import java.util.*;
public class Main{
public static void main (String [] args){
Scanner in = new Scanner(System.in);
int times = in.nextInt();
Long ans = 1L;
int [] arr = new int [times];
for (int i = 0; i < times; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
ans*=(arr[i]-i);
ans=ans%((int)Math.pow(10, 9)+7);
}
System.out.println(ans%((int)Math.pow(10, 9)+7));
}
}
