URAL/1523

来自"NOCOW"

树状数组就行，做k-1次传统逆序对即可。

#include <cstdio>
#include <cstring>
#define lowbit(x) ((x)&(-x))
typedef long long LL;
const LL p=1000000000LL;
int n,k,now=0,a[20001];
LL sum,ans=0,f[2][20001]={0},g[2][20001]={0};
void modify(int x,LL v)
{
    for (;x;x-=lowbit(x))
        f[now][x]=(f[now][x]+v)%p;
}
LL query(int x)
{
    for (sum=0;x<=n;x+=lowbit(x))
        sum=(sum+f[now][x])%p;
    return sum;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;g[1][i++]=1)  scanf("%d",a+i);
    for (int i=2;i<=k;++i,now^=1)
    {
        memset(f[now],0,sizeof(f[now]));
        for (int j=i-1;j<=n;++j)
        {
            modify(a[j]-1,g[now^1][j]);
            g[now][j]=query(a[j]);
        }
    }
    for (int i=k;i<=n;++i)  ans=(ans+g[now^1][i])%p;
    printf("%I64d\n",ans);
    return 0;
}
//by zzy
<source>