백준 13555 - 증가하는 부분 수열

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

 

17409 - 증가 수열의 개수와 풀이가 같다.

 

다만 17409와 달리 원소의 상한과 수열의 길이가 불일치라는 것과 세그먼트 트리가 아닌 펜윅 트리로만 풀린다는 점을 유의하여 구현하도록 한다.

 

전체 코드

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

#include <bits/stdc++.h>

using namespace std;

#define mod 5000000

int n, k;
int dp[51][100001];

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

    int 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 <= 100000)
    {
        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(100000, k);
}