C - Not Equal Editorial by blackyuki
解けない問題にあたった時、具体例を考えてみるという戦略はどの問題においても有用です。
本解説では具体例として、\(C=(100,100,100)\) の場合を考えてみます。
まず、\(A_1\) の値としてありうるのは \(1,2, \ldots ,100\) の \(100\) 通りです。
次に、\(A_2\) の値としてありうるのは \(1,2, \ldots ,100\) から \(A_1\) としてすでに用いた \(1\) つを取り除いた \(99\) 通りです。
最後に、\(A_3\) の値としてありうるのは \(1,2, \ldots ,100\) から \(A_1,A_2\) としてすでに用いた \(2\) つを取り除いた \(98\) 通りです。
よって \(A\) としてありうるのは \(100 \times 99 \times 98\) 通りと求められます。
同じように考えると \(C\) が昇順に並んでいるとき、条件を満たす \(A\) の個数は \((C_i-i+1)\) を掛け合わせた値であることが分かります。証明としては、\(A_1, A_2, \ldots \) の順に値を決めていったときに、\(A_i\) の値の候補が \(1,2, \ldots C_i\) から \(A_1, A_2, \ldots A_{i-1}\) (これらは相異なり、全て \(1\) 以上 \(C_i\) 以下) を除いた計 \(C_i-i+1\) 個であるからです。ただし、\(C_i-i+1<0\) となる \(i\) が一つでも存在すれば答えは \(0\) です。
なお、入力で与えられる \(C\) は昇順に並んでいるとは限らないので昇順に並び替える必要があります。
32-bit 型を用いると計算途中でオーバーフローしてしまう可能性があることに注意してください。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<int> C(N);
for(int i = 0; i < N; i++) cin >> C[i];
sort(C.begin(),C.end());
long long ans = 1;
for(int i = 0; i < N; i++) ans = ans * max(0, C[i] - i) % 1000000007;
cout << ans << endl;
}
実装例 (Python)
N = int(input())
C = list(map(int, input().split()))
C.sort()
ans=1
for i in range(N):
ans = ans * max(0, C[i] - i) % 1000000007
print(ans)
posted:
last update: