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

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 #define mod 1000000000
 6 int a[22000],sum[22000][15];
 7 int p[22000],n;
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 void update(int x,int z)
13 {
14     while(x)
15     {
16         p[x]=(p[x]+z)%mod;
17         x-=lowbit(x);
18     }
19 }
20 int query(int x)
21 {
22     long long s=0;
23     while(x<=n)
24     {
25         s+=p[x];
26         s%=mod;
27         x+=lowbit(x);
28     }
29     return s;
30 }
31 int main()
32 {
33     //freopen("in.txt","r",stdin);
34     int k,i,j;
35     scanf("%d%d",&n,&k);
36     memset(sum,0,sizeof(sum));
37     for(i=1;i<=n;i++)
38     scanf("%d",&a[i]),sum[a[i]][1]=1;
39     for(i=2;i<=k;i++)
40     {
41         memset(p,0,sizeof(p));
42         for(j=i-1;j<=n;j++)
43         {
44             update(a[j],sum[a[j]][i-1]);
45             sum[a[j]][i]=query(a[j]+1);
46         }
47     }
48     long long s=0;
49     for(i=k-1;i<=n;i++)
50     {
51         s=(s+sum[a[i]][k])%mod;
52     }
53     cout<<s<<endl;
54 }