Not Equal [AtCoder Beginner Contest 209 C]

https://atcoder.jp/contests/abc209/tasks/abc209_c

前提知識

• modつき計算

解説

https://atcoder.jp/contests/abc209/submissions/24156090

問題をそのまま受け取ると難しい問題。
mod 10⁹ + 7での計算ができることが前提条件。
とりあえず解きたい場合はAC Library Modintを使って解いてもいいと思う。

条件を見直す

条件が2つである。

• 1～Cの範囲内に数を収める必要がある
• もう1つ数をかぶらせることができない

ここで1つ思考のbreakthroughを起こす必要がある。
それは「数を割り当てる順番に特に指定はない」ということである。

競技プログラミングのテクとして、配列のソートができる場合はソートすることで解ける場合があるというのがある。
今回の配列Cはソートをしたものを考えても最終的な答えは変わらない。
今後、配列Cはソート済みであると仮定する。

ソート後はどうか

ソートした後に先頭から順番に決めていくことにする。
最初の数A[0]は1≦A[0]≦C[0]となり、これはC[0]通りの組み合わせがある。

2番目の数A[1]は1≦A[1]≦C[1]、かつ、A[0]でない数である。
配列Cはソート済みなので、A[0]は必ず1からC[1]の間にあることが分かる。
よって、組合せはC[1]-1通りの組み合わせとなる。

3番目の数A[2]は1≦A[2]≦C[2]、かつ、A[0]でもA[1]でもない数である。
配列Cはソート済みなので、A[0],A[1]は必ず1からC[2]の間にあることが分かる。
よって、組合せはC[2]-2通りの組み合わせとなる。

これを順番に行っていけば、各部分の組み合わせが求められるので、総積を取れば答えになる。

int N, C[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> C[i];
    sort(C, C + N);
    
    mint ans = 1;
    rep(i, 0, N) ans *= C[i] - i;
    cout << ans << endl;
}