증가 수열의 개수 (백준 17409)

안녕하세요. 오늘은 증가 수열의 개수를 셀 거예요.

문제

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

아이디어

dp[K][N]을 arr[N]으로 끝나고 길이가 K인 증가수열의 개수라고 정의합시다.
그러면 dp[K][N]은 arr[j]<arr[N]인 모든 j에 대해서 dp[K-1][j]의 합으로 정의할 수 있습니다.
그리고 이 값은 세그먼트 트리를 통해서 빠르게 자신보다 작은 값들의 합을 구할 수 있습니다.
이 방법을 그대로 해주면 됩니다.
1. dp[0][0]=1
2. 세그트리에 dp[i-1][j]값을 갱신시키고
3. dp[i][j]를 구하기
4. 모든 j에 대해서 끝났으면 세그트리 초기화

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[404040] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = 0;
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx, ll val) //idx번지에 val만큼 더하기
{
    if (e < idx || idx < s) return;
    tree[node] += val;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, val);
    change(mid + 1, e, node * 2 + 1, idx, val);
}

ll dp[11][101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, K, i, j, arr[101010] = { 0 };

    cin >> N >> K;
    for (i = 1; i <= N; i++) cin >> arr[i];

    change(0, N, 1, 0, 1); //dp[0][0]=1
    for (i = 1; i <= K; i++)
    {
        for (j = 1; j <= N; j++)
        {
            change(0, N, 1, arr[j], dp[i - 1][j]);
            dp[i][j] = SUM(0, N, 1, 0, arr[j] - 1);
            dp[i][j] %= 1000000007;
        }
        init(0, N, 1);
    }
    
    ll ans = 0;
    for (i = 1; i <= N; i++)
    {
        ans += dp[K][i];
        ans %= 1000000007;
    }
    cout << ans;
}

감사합니다.