C. Subsequences

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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.

Output

Print one integer — the answer to the problem.

Examples

input

5 2
1
2
3
5
4

output

7                                                                                                                   

Now, this type of question is a simple DP problem. The state of which can be visualized as 

dp[i][k] which tells the number of sequences that ends at ith index of the array such that 

the length of the sequence is k. 

To be specific we solve this problem by sorting all the numbers along with their indexes. Now

supose the array is 2 1 3 7 4 

the new array along with indexes looks like

                            1 2 3 4 7 

                            2 1 3 5 4

If we access this element from left to right the one thing which we are sure about it

all elements that are smaller that it has been accessed. Now the recurrence can be simply

seen as dp[i][k]= sum(dp[0......i-1][k-1]) where i stands for the current index.

              *****************THE CODE RUNS HERE ********************************

 #include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long int 
ll dp[600010][20];
bool cmp(pair<int,int> &a ,pair<int,int> &b)
{
     if(a.ff<b.ff)
     return 1;
     else if(a.ff==b.ff)
     return a.ss>b.ss;
     return 0;
}
void update(int node,int k,int s,int e,int low,int high,ll val)
{
    if(s>e || low>e || s>high)
    return ;
    if(s>=low && e<=high)
    {
                 dp[node][k]+=val;
                 return ;
    }
    int mid=(s+e)/2;
    update(2*node,k,s,mid,low,high,val);
    update(2*node+1,k,mid+1,e,low,high,val);
    dp[node][k]=dp[2*node][k]+dp[2*node+1][k];
}
ll query(int node,int k,int s,int e,int low,int high)
{
    if(s>e || s>high || e<low)
    return 0;
    if(s>=low && e<=high)
    {
       return dp[node][k];
    }
    int mid=(s+e)/2;
    ll q1=query(2*node,k,s,mid,low,high);
    ll q2=query(2*node+1,k,mid+1,e,low,high);
    ll res=q1+q2;
    return res;
}
int main()
{
   int n;
   cin>>n;
   int k;
   cin>>k;
   k++;
   vector<pair<int,int> > v;
   for(int i=0;i<n;i++)
   {
      int xx;
      cin>>xx;
      v.push_back(make_pair(xx,i+1));
   }
   sort(v.begin(),v.end());
   update(1,0,0,n,0,0,1);
   for(int i=1;i<=n;i++)
   {
       int idx=v[i-1].second;
      for(int c=1;c<=k;c++)
      {
               ll ret=query(1,c-1,0,n,0,idx-1);
       update(1,c,0,n,idx,idx,ret);   
    }
   }
   ll ans=0;
   for(int i=1;i<=n;i++)
   {
         ans+=query(1,k,0,n,i,i);
   }
   cout<<ans<<endl;
}

Similar Problem 

http://www.spoj.com/problems/INCSEQ/

Here we are required to find the same thing but the subsequence should be strictly increasing.

Solution

Its just a modification of the first question, where we slightly change the order of the data 

such that if the values are equal larger indexes comes first. This helps us to remove the ambiguity.

******************** THE CODE RUNS HERE *****************************************

 #include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long int 
int dp[600010][56];
#define mod 5000000
bool cmp(pair<int,int> &a ,pair<int,int> &b)
{
     if(a.ff<b.ff)
     return 1;
     else if(a.ff==b.ff)
     return a.ss>b.ss;
     return 0;
}
void update(int node,int k,int s,int e,int low,int high,int val)
{
    if(s>e || low>e || s>high)
    return ;
    if(s>=low && e<=high)
    {
                 dp[node][k]+=val;
                 if(dp[node][k]>=mod)
                 dp[node][k]%=mod;
                 return ;
    }
    int mid=(s+e)/2;
    update(2*node,k,s,mid,low,high,val);
    update(2*node+1,k,mid+1,e,low,high,val);
    dp[node][k]=dp[2*node][k]+dp[2*node+1][k];
    if(dp[node][k]>=mod)
    dp[node][k]%=mod;
}
int query(int node,int k,int s,int e,int low,int high)
{
    if(s>e || s>high || e<low)
    return 0;
    if(s>=low && e<=high)
    {
       return dp[node][k];
    }
    int mid=(s+e)/2;
    int q1=query(2*node,k,s,mid,low,high);
    int q2=query(2*node+1,k,mid+1,e,low,high);
    int res=(q1+q2);
    if(res>=mod)
    res%=mod;
    return res;
}
int main()
{
   int n;
   cin>>n;
   int k;
   cin>>k;
   vector<pair<int,int> > v;
   for(int i=0;i<n;i++)
   {
      int xx;
      cin>>xx;
      v.push_back(make_pair(xx,i+1));
   }
   sort(v.begin(),v.end(),cmp);
//   for(int i=0;i<n;i++)
//   {
//     cout<<v[i].ff<<" ";
//   }
//   cout<<endl;
//   for(int i=0;i<n;i++)
//   {
//      cout<<v[i].ss<<" ";
//   }
  // cout<<endl;
   update(1,0,0,n,0,0,1);
   for(int i=1;i<=n;i++)
   {
       int idx=v[i-1].second;
      for(int c=1;c<=k;c++)
      {
               int ret=query(1,c-1,0,n,0,idx-1);
               if(ret>=mod)
      ret%=mod;
       update(1,c,0,n,idx,idx,ret);   
    }
   }
   int ans=0;
   for(int i=1;i<=n;i++)
   {
         ans+=query(1,k,0,n,i,i);
         if(ans>=mod)
         ans%=mod;
   }
   cout<<ans<<endl;
}