백준 17927 (C++) Counting Greedily Increasing Supersequences

최초 업로드: 2025-10-25 11:19:47

최근 수정 시간: 2025-10-25 11:19:47

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] Counting Greedily Increasing Supersequences

[문제 링크](https://www.acmicpc.net/problem/17927)

## 문제 설명

Given a permutation $A = (a_1, a_2, \dots, a_N)$ of the integers $1, 2, \dots, N$, we define the greedily increasing subsequence (GIS) in the following way.

Let $g_1 = a_1$. For every $i > 1$, let $g_i$ be the leftmost integer in $A$ that is strictly larger than $g_{i-1}$. If for a given $i$ there is no such integer, we say that the GIS of the sequence is the sequence $(g_1, g_2, ..., g_{i - 1})$.

For example, consider the permutation $(2, 3, 1, 5, 4, 7, 6)$. First, we have $g_1 = 2$. The leftmost integer larger than $2$ is $3$, so $g_2 = 3$. The leftmost integer larger than $3$ is $5$ ($1$ is too small), so $g_3 = 5$. Finally, $g_4 = 7$. Thus, the GIS of $(2, 3, 1, 5, 4, 7, 6)$ is $(2, 3, 5, 7)$.

Given a sequence $G = (g_1, g_2, \dots, g_L)$, how many permutations $A$ of the integers $1, 2, \dots, N$ have $G$ as its GIS?

## 입력

The first line of input contains the integers $1 \le N \le 10^6$, the number of elements of the permutation $A$, and $1 \le L \le 10^6$, the length of the sequence $G$.

The next line contains $L$ positive integers between $1$ and $N$, the elements $g_1, \dots, g_L$ of the sequence $G$.

## 출력

Output a single integer: the number of $N$-element permutations having the given sequence as its GIS. Since this number may be large, output it modulo the prime number $10^9 + 7$.

## 풀이
N부터 1까지 처음으로 해당 수의 개수 + 이전에 넣은 수의 개수를 다 곱해주면 됩니다. 만약 G 수열의 마지막 수가 N이 아니거나 올바르지 않은 G 수열이 들어오는 경우 불가능합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, l; cin >> n >> l;
 vector<int> arr(l);
 for(int i=0;i<l;i++) {
 cin >> arr[i];
 if(i && arr[i-1]>=arr[i]) {
 cout << 0;
 return 0;
 }
 }

if(arr.back()!=n) {
 cout << 0;
 return 0;
 }

ll ret=1, cnt=0;
 for(int i=n;i>=1;i--) {
 auto low = lower_bound(arr.begin(), arr.end(), i);
 if(*low!=i) ret = ret*(arr.end()-low+cnt++)%MOD;
 }
 cout << ret;
}
```