백준 17409 - 증가 수열의 개수

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

Intro

적당히 작은 N에 대해서는 DP[k][n] := n번째 수에서 LIS의 길이가 k인 경우의 수로 정의하여 $O(KN^{2})$ DP로 해결할 수 있다고 알려져 있다. 스택 오버플로우

 

다만 이 문제에서는 $N \leq 100000$ 이므로 무식하게 다중 반복문을 돌릴 수 없을 것이다. 어떻게 해야 할까?

아이디어

이 게시글 중반부에서 LIS를 세그먼트 트리로 구하는 법을 소개하고 있다. 이를 잘 응용하면 naive 한 DP를 수행하는데 걸리는 $O(N^{2})$ 시간 복잡도를 $O(N \log N)$으로 줄여볼 수 있지 않을까?

 

우리는 세그먼트 트리를 이용하여 n 이하의 수로 이루어지고 길이가 k의 수열의 개수를 관리할 것이다.

 

이는 세그먼트 트리로 2차원 배열을 이용해 다음과 같이 나타낼 수 있다.

 

dp[k][n] := 길이가 k인 수열 원소 값 n 이하 구간에서 각 원소가 출현한 횟수

 

그러면 n 이하의 수로 이루어지고 길이가 k인 수열의 개수는 n - 1 이하의 수로 이루어지고 길이가 k - 1인 수열의 개수에서 전이하는 관계를 생각해볼 수 있다.

 

이렇게 했을 때 n, k -> n + 1, k + 1 -> n + 2, k + 2... 이렇게 구성적으로 길이가 k인 LIS의 개수를 알 수 있다.

 

그렇다면 $O(\log N)$의 시간 복잡도로 dp[k - 1][n - 1]을 dp[k][n]으로 전이하는 방법을 생각해보자. 이는 세그먼트 트리의 더하기 연산을 이용하여 처리할 수 있다.

 

전이를 구현하는 데는 펜윅 트리가 사용하기 좋다.

 

입력받은 원소 x에 대해 k의 길이만큼 반복문을 돌리면서 x보다 작은 원소가 나오는 횟수를 sum()으로 구하여 x, k + 1 테이블에 이를 add()로 반영해주면 빠르게 테이블을 전이시킬 수 있다.

 

그러면 $O(NK \log N)$의 시간 복잡도로 모든 구간에 대한 테이블을 완성할 수 있고 10만 이하의 원소를 포함하는 전체 구간에서 길이가 k인 LIS의 개수를 sum() 함수로 구하면 된다!

구현

위에서 말한 대로 펜윅 트리를 사용하였다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define mod 1000000007

int n, k;
ll dp[11][100001];

ll sum(int pos, int seq)
{
    if (!seq)
        return 1;

    ll ret = 0;

    while (pos)
    {
        ret += dp[seq][pos];
        ret %= mod;
        pos &= (pos - 1);
    }

    return ret;
}

void add(int pos, int seq, int val)
{
    while (pos <= n)
    {
        dp[seq][pos] += val;
        dp[seq][pos] %= mod;
        pos += (pos & -pos);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        for (int j = 1; j <= k; ++j)
            add(x, j, sum(x - 1, j - 1));
    }

    cout << sum(n, k);
}