incseq.cpp 1003 Bytes
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
#include <cstdio>

#define MAXK 55
#define MAXVAL 100005
#define MOD 5000000

int bit[MAXK][MAXVAL], N, K;

void Add ( int b, int pos, int val ) {
    while ( pos < MAXVAL ) {
        bit[b][pos] = ( bit[b][pos] + val ) % MOD;
        pos += pos & -pos;
    }
}

int Sum ( int b, int pos ) {
    int s = 0;
    while ( pos > 0 ) {
        s = ( s + bit[b][pos] ) % MOD;
        pos -= pos & -pos;
    }
    return s;
}

int main ( void ) {
    //freopen ("input","r",stdin);
    int i, j, tmp, ans;

    scanf ("%d %d", &N, &K);
    
    if ( K == 1 ) {
        printf ("%d\n", N );
        return 0;
    }

    for ( i=1; i<=N; ++i ) {
        scanf ("%d", &tmp );
        ++tmp;
        Add ( 1, tmp, 1 );
        for ( j=1; j<K; ++j ) {
            ans = Sum ( j, tmp-1 );
            if ( ans == 0 ) {
                break;
            }
            Add ( j+1, tmp, ans );
        }
    }

    printf ("%d\n", Sum ( K, MAXVAL ) );

    return 0;
}