13556번: 증가하는 부분 수열 2

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

$O(kn\lg n)$

dp[i][j]: 길이 i이고 a[j]로 끝나며 dp[i][1...j-1]에 포함되지 않는 증가 부분 수열 개수
dp[i][j] = sum(k<j, a[k]<a[j])(dp[i-1][k]) - sum(k<j,a[k]=a[j])(dp[i][k])
fenwick tree를 이용한다.

#include<cstdio>
#include<cstring>
#define mod 5000000
int n, k, bit[100001], a[100000], dp[100000], t[100001];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i), dp[i] = !t[a[i]]++;
    for (int i = 2; i <= k; i++) {
        memset(bit, 0, sizeof(bit));
        memset(t, 0, sizeof(t));
        for (int j = 0; j < n; j++) {
            for (int h = a[j]; h <= 1e5; h += h&-h) bit[h] = (bit[h] + dp[j]) % mod;
            dp[j] = mod - t[a[j]];
            for (int h = a[j] - 1; h; h -= h&-h) dp[j] = (dp[j] + bit[h]) % mod;
            t[a[j]] = (t[a[j]] + dp[j]) % mod;
        }
    }
    int s = 0;
    for (int i = 0; i < n; i++) s = (s + dp[i]) % mod;
    printf("%d", s);
    return 0;
}