5회 문제풀이 01 / ABC 209 C - Not Equal
ABC 209 C - Not Equal
【문제 개요】
길이 N의 정수열 C가 주어집니다. 이하의 조건을 전부 만족하는 길이 N의 정수열 A의 개수를 구하시오.
- 1 ≤ Aᵢ ≤ Cᵢ(1 ≤ i ≤ N)
- Aᵢ ≠ Aⱼ (1 ≤ i < j ≤ N) 단, 답변이 엄청나게 커질 가능성이 있기때문에 (10⁹ + 7)으로 나눈 나머지를 출력하시오.
힌트 : 조합론적 접근, 모듈러 연산
【전제】
- 입력은 모두 정수이다.
- 1 ≤ N ≤ 2 x 10⁵
- 1 ≤ Cᵢ ≤ 10⁹
【입력 형태】
1
2
N
C₁ C₂ ... Cₙ
【출력 형태】
조건을 전부 만족하는 정수열 A의 개수를 (10⁹ + 7)로 나눈 나머지를 출력하라.
【예시】
입력 예 1
1
2
2
1 3
출력 예 1
1
2
조건을 전부 만족하는 A는 (1, 2)와 (1, 3)의 2개이다. 예를들어 (1, 1)는 2번째 조건을 만족하지 않으며, (2, 3)은 1번째 조건을 만족하지 않는다.
입력 예 2
1
2
4
3 3 4 4
출력 예 2
1
12
입력 예 3
1
2
2
1 1
출력 예 3
1
0
조건을 만족하는 정수열이 1개도 없기때문에 0이 출력된다.
입력 예 4
1
2
10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979
출력 예 4
1
405924645
(10⁹ + 7)로 나눈 나머지를 출력하는것에 주의하라.
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。