codeforces 597C - Subsequences

枚举子序列的末尾，递推。

方案数：f[i = 以i结尾][k =子序列长度] = sum(f[j][k-1])，j < i。

转移就建立k个BIT。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+, K = ;

ll C[K][N];

ll sum(ll C[],int x)

{

    ll re = ;

    while(x > ){

        re += C[x]; x &= x-;

    }

    return re;

}

int n;

void add(ll C[],int x,ll d)

{

    while(x <= n){

        C[x] += d; x += x&-x;

    }

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int k;

    cin>>n>>k;

    if(k == ) { cout<<n; return ;}

    k--;

    ll ans = ;

    for(int i = ,j,x; i < n; i++){

        scanf("%d",&x);

        ans += sum(C[k],x);

        for(j = k; j > ; j--){

            add(C[j],x,sum(C[j-],x));

        }

        add(C[],x,);

    }

    cout<<ans<<endl;

    return ;

}