For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.
First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.
Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.
Print one integer — the answer to the problem.
5 2
1
2
3
5
4
7
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100100; const int INF=(1<<29); int n,k; ll a[maxn]; ll c[maxn][15]; int lowbit(int x) { return x&(-x); } ll sum(int p,int id) { ll res=0; while(p>0){ res+=c[p][id]; p-=lowbit(p); } return res; } void add(int p,int id,ll x) { while(p<=n){ c[p][id]+=x; p+=lowbit(p); } } int main() { ///freopen("in.txt","r",stdin); while(cin>>n>>k){ REP(i,1,n) scanf("%I64d",&a[i]); MS0(c); REP(i,1,n){ add(a[i],1,1); REP(j,2,k+1) add(a[i],j,sum(a[i]-1,j-1)); } cout<<sum(n,k+1)<<endl; } return 0; } →Judgement Protocol
codeforces test #12 C. Subsequences 树状数组统计
原文：http://www.cnblogs.com/--560/p/4959618.html
