[BOJ 17927] Counting Greedily Increasing Supersequences

https://www.acmicpc.net/problem/17927

17927번: Counting Greedily Increasing Supersequences

Tag : combinatorics, number theory

문제요약

수열 $A$의 GIS는 $A_1$을 시작으로 각 $G_i$가 $A_j$일 때 $j$보다는 오른쪽에 있으며 $G_i$보다 큰 가장 왼쪽의 원소가 $G_{i+1}$가 된다. 수열 $G$가 주어졌을 때 이를 GIS로 가지는 $A$의 가짓수를 구하는 문제이다.

 

풀이

나의 생각의 흐름을 가능한 자세히 적어보겠다.

 

관찰 1)

$G$는 오름차순이어야하며 이를 만족하지 않으면 답은 0이다.

 

관찰 2)

각 $A_i$가 위치할 수 있는 자리는 $G$에서 $A_i$보다 큰 원소의 오른쪽부터 가장 오른쪽의 위치까지다.

그러면 각 원소가 위치할 수 있는 범위가 $[L_{A_i},inf]$과 같이 정해진다.

 

관찰 3)

다음과 같이 구간을 나눠본다면 원소들이 위치할 수 있는 곳의 후보군은 $G$의 크기와 같다.

들어갈 수 있는 범위가 $[G_i,inf]$인 원소의 개수를 $C_i$라 정의하겠다.

우선 $C_5$에 대해서만 정답을 생각해보면 $C_i!$이다. $C_4$까지 고려하면 어떻게 될까?

$C_4$개의 원소들이 들어갈 수 있는 곳은 고정된 점들 + 1이기 때문에 각각 $C_5+2$, $C_5+3$, $C_5+4$,...,$C_5+C_4+1$개다. 이것과 $C_5$에서의 답을 곱한 것이 $C_4$의 답이 되며 이 방식대로 $C_1$까지 계산해나가면된다.

 

시간복잡도 : $O(N)$

 

전체 코드

 

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;

namespace BINOM{
    const ll MOD=(ll)1e9+7;
    ll factorial[4'000'000 + 5], inverse[4'000'000 + 5];
    ll fpow(ll a, ll m) {
        if (m == 0) return 1;
        ll next = fpow(a, m / 2);
        next = next * next % MOD;
        if (m % 2) return next * a % MOD;
        else return next;
    }
    ll nPr(int n, int k){
        if(n<k)return 0;
        return factorial[n] * inverse[n-k] % MOD;
    }
    ll nCr(int n, int k) {
        if(n<k)return 0;
        return nPr(n, k) * inverse[k] % MOD;
    }
    void init(){
        factorial[0] = 1;
        for (int i = 1; i <= 4000000; i++) factorial[i] = factorial[i - 1] * i % MOD;
        inverse[4000000] = fpow(factorial[4000000], MOD - 2);
        for (int i = 3'999'999; i >= 0; i--) inverse[i] = inverse[i + 1] * (i + 1) % MOD;
    }
}
using namespace BINOM;

ll N,L,ans=1;
ll G[1010101];
ll v[1010101];
ll cnt[1010101];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    init();
    cin>>N>>L;
    for(int i=1;i<=L;i++){
        cin>>G[i];
        v[G[i]]=-1;
    }
    for(int i=2;i<=L;i++)if(G[i]<=G[i-1]){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=N;i++){
        if(v[i]==-1)continue;
        if(G[L]<i){
            cout<<0<<endl;
            return 0;
        }
        v[i]=upper_bound(G+1,G+1+L,i)-G;
        cnt[v[i]]++;
    }
    ll sum=0;
    for(ll i=L;i>=1;i--){
        if(cnt[i]==0)continue;
        ll t=factorial[L-i+cnt[i]+sum]*inverse[L-i+sum]%MOD;
        ans=ans*t%MOD;
        sum+=cnt[i];
    }
    cout<<ans<<endl;
}