P1866. 编号

发表于 分类于 阅读次数： Waline： 本文字数： 231 阅读时长 ≈ 1 分钟

考点

  • 排序
  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e3 + 50, MOD = 1e9 + 7;
int n, arr[LEN];

int main() {
  long long ans = 1;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> arr[i];
  sort(arr, arr + n);
  for (int i = 0; i < n; ++i) ans = (ans * (arr[i] - i)) % MOD;
  cout << ans;
  return 0;
}

思路

就拿样例来说吧

  • 5在前，8在后时

    组合数为 \[ C\begin{array}{c} 1\\ 5\\ \end{array}\cdot C\begin{array}{c} 1\\ 7\\ \end{array} \]

  • 8在前，5在后时

    组合数为 \[ \underset{6-8\text{里选}}{\underbrace{C\begin{array}{c} 1\\ 3\\ \end{array}}}\cdot \underset{1-5\text{里选}}{\underbrace{C\begin{array}{c} 1\\ 5\\ \end{array}}}+\underset{1-5\text{里选}}{\underbrace{C\begin{array}{c} 1\\ 5\\ \end{array}}}\cdot \underset{1-4\text{里选}}{\underbrace{C\begin{array}{c} 1\\ 4\\ \end{array}}} \]

可以发现两者是完全一样的，顺序不影响最终的结果

从小到大排序后，每次都乘上arr[i] - i，即当前可能性 = 当前可选 - 之前已选