1523. K-inversions
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Consider a permutation a1, a2, …, an (all ai are different integers in range from 1 to n). Let us call k-inversion a sequence of numbers i1, i2, …, ik such that 1 ≤ i1 < i2 < … < ik ≤ n andai1 > ai2 > … > 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 109.
Samples
| input | output |
|---|---|
3 2 |
2 |
5 3 |
10 |
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define mod 1000000000
int a[],sum[][];
int p[],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=;
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,,sizeof(sum));
for(i=;i<=n;i++)
scanf("%d",&a[i]),sum[a[i]][]=;
for(i=;i<=k;i++)
{
memset(p,,sizeof(p));
for(j=i-;j<=n;j++)
{
update(a[j],sum[a[j]][i-]);
sum[a[j]][i]=query(a[j]+);
}
}
long long s=;
for(i=k-;i<=n;i++)
{
s=(s+sum[a[i]][k])%mod;
}
cout<<s<<endl;
}