1523. K-inversions

Time limit: 1.0 second Memory limit: 64 MB

Consider a permutation

 

a

₁,

 

a

₂, …,

 

a_n

 (all

 

a_i

 are different integers in range from 1 to

 

n). Let us call

 

k-inversion

 a sequence of numbers

 

i

₁,

 

i

₂, …,

 

i_k

 such that 1 ≤ 

i

₁ < 

i

₂ < … < 

i_k ≤ 

n

 and

 

a_i

₁ > 

a_i

₂ > … > 

a_ik. 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

 

a_i.

Output

Output a single number — the number of

 

k-inversions in a given permutation. The number must be taken modulo 10

⁹.

Samples

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

Problem Author: Dmitry Gozman

Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January

************************************************************************************************

树状数组（加快运算时间）

************************************************************************************************

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 using namespace std; 8 const int N=20005; 9 const int MOD=1000000000;10 int a[N],dp[2][N];11 int c[N];12 int i,j,k,n;13 int sum;14 int lowbit(int x)//低位技术15 {16 return x&(-x);17 }18 void insert(int x,int v)//修改19 {20 for(;x<=n;x+=lowbit(x))21 c[x]=(c[x]+v)%MOD;22 }23 int query(int x)//查询24 {25 int suma=0;26 for(;x>0;x-=lowbit(x))27 suma=(suma+c[x])%MOD;28 return suma;29 }30 int main()31 {32 cin>>n>>k;33 for(i=1;i<=n;i++)34 {35 cin>>a[i];36 dp[1][i]=1;37 }38 int now=0;39 for(i=1;i
              
               MOD)sum-=MOD;51 52 }53 }54 sum=0;55 for(i=k;i<=n;i++)56 sum=(sum+dp[now^1][i])%MOD;57 if(sum>MOD)sum-=MOD;58 cout<
               
                <