1523. K-inversions URAL 求k逆序对，，，，DP加树状数组

1523. K-inversions

Time limit: 1.0 second
Memory limit: 64 MB

Consider a permutation  a 1,  a 2, …,  an (all  ai are different integers in range from 1 to  n). Let us call  k-inversion a sequence of numbers  i 1,  i 2, …,  ik such that 1 ≤  i 1 <  i 2 < … <  ik ≤  n and ai 1 >  ai 2 > … >  aik. Your task is to evaluate the number of different  k-inversions in a given permutation.

Input

The first line of the input contains two integers  n and  k (1 ≤  n ≤ 20000, 2 ≤  k ≤ 10). The second line is filled with  n numbers  ai.

Output

Output a single number — the number of  k-inversions in a given permutation. The number must be taken modulo 10 9.

Samples

input	output
3 2 3 1 2	2
5 3 5 4 3 2 1	10

 

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define mod 1000000000
int a[22000],sum[22000][15];
int p[22000],n;
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int z)
{
    while(x)
    {
        p[x]=(p[x]+z)%mod;
        x-=lowbit(x);
    }
}
int query(int x)
{
    long long s=0;
    while(x<=n)
    {
        s+=p[x];
        s%=mod;
        x+=lowbit(x);
    }
    return s;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int k,i,j;
    scanf("%d%d",&n,&k);
    memset(sum,0,sizeof(sum));
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]),sum[a[i]][1]=1;
    for(i=2;i<=k;i++)
    {
        memset(p,0,sizeof(p));
        for(j=i-1;j<=n;j++)
        {
            update(a[j],sum[a[j]][i-1]);
            sum[a[j]][i]=query(a[j]+1);
        }
    }
    long long s=0;
    for(i=k-1;i<=n;i++)
    {
        s=(s+sum[a[i]][k])%mod;
    }
    cout<<s<<endl;
}