2015年11月4日 星期三

2015/11/04 UVA 12983 - The Battle of Chibi

/* https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4866 */
/*
    我應該要用BIT來寫的
    因為遞迴很慢 
    線段樹如果是做N*M次查詢
    而不是查N次每次查M個 會TLE

    用線段樹 對區間 [i,j) 維護 num[k]
    代表說 結尾數值 在[i,j)中
    長度為k的遞增序列的個數
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

#define MOD (int)(1e9+7)

int N, M;

struct node
{
    node *l, *r;
    int num[1001];

    node()
    {
        l = r = NULL;
        for(int Mi = 1; Mi <= M; Mi++) num[Mi] = 0;
    }
};

node mem[2000]; int clk = 0;

int num[1001];

node* get(){ mem[clk] = node(); return mem+(clk++); }

node* build(int L, int R)
{
    node *r = get();

    if( L+1 < R )
    {
        r->l = build(L, (L+R)/2);
        r->r = build((L+R)/2, R);
    }

    return r;
}

void add(node *O, int L, int R, int x)
{
    if( x+1 <= L || R <= x ) return;
    else if( x <= L && R <= x+1 )
    {
        for(int Mi = 1; Mi <= M; Mi++)
            O->num[Mi] += num[Mi], O->num[Mi] %= MOD;
    }
    else
    {
        add(O->l, L, (L+R)/2, x);
        add(O->r, (L+R)/2, R, x);

        for(int Mi = 1; Mi <= M; Mi++)
        {
            O->num[Mi] = O->l->num[Mi]+O->r->num[Mi];
            O->num[Mi] %= MOD;
        }
    }
}

void ask(node *O, int L, int R, int A, int B)
{
    if( B <= L || R <= A );
    else if( A <= L && R <= B )
    {
        for(int Mi = 1; Mi <= M; Mi++)
        {
            num[Mi] += O->num[Mi];
            num[Mi] %= MOD;
        }
    }
    else
    {
        ask(O->l, L, (L+R)/2, A, B);
        ask(O->r, (L+R)/2, R, A, B);
    }
}

int A[1000];
node *root;

int main()
{
    int T;
    scanf("%d", &T);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        clk = 0;

        scanf("%d %d", &N, &M);

        vector<int> v;

        for(int Ni = 0; Ni < N; Ni++)
            scanf("%d", &A[Ni]), v.push_back(A[Ni] );

        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end())-v.begin() );

        map<int, int> m;

        for(int vi = 0; vi < v.size(); vi++)
            m[v[vi] ] = vi;

        for(int Ni = 0; Ni < N; Ni++)
            A[Ni] = m[A[Ni] ];

        root = build(0, N);

        for(int Ni = 0; Ni < N; Ni++)
        {
            for(int Mi = 1; Mi <= M; Mi++) num[Mi] = 0;
            ask(root, 0, N, 0, A[Ni]);

            for(int Mi = M; Mi >= 2; Mi--)
                num[Mi] = num[Mi-1];

            num[1] = 1;

            add(root, 0, N, A[Ni]);
        }

        for(int Mi = 1; Mi <= M; Mi++) num[Mi] = 0;
        ask(root, 0, N, 0, N);
        printf("Case #%d: %d\n", Ti,  num[M]);
    }
}

沒有留言:

張貼留言