回去想的，用全排列，逐个搜索
#include<stdio.h>
int p[4000000][100];//保存剩余数的全排列
int num=0;//保存剩余数全排列个数
int count=0;//保存i<j,a[i]<a[j]的个数
void swap(int &a,int &b)
{
int t;
t=a;
a=b;
b=t;
}
//求剩余数的个数
int less(int *a,int *b,int
n)//扫描b[n],如果有b[j]=a[i],b中从j开始每项往前面移一位 ,s记录b中剩余个数；
{
int i,j,k,s=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(a[i]==0) break;
if(b[j]==a[i])
{
s--;
for(k=j;k<n-1;k++)
{
b[k]=b[k+1];
}
break;
}
}
return s;
}
//剩余的数全排列
void perm(int a[],int start,int
n)//a[n]数组从a[start]开始全排列，结果放在b[num][n]中 ，num计数
{
int i;
int *c;
if(start==n-1)
{
for(i=0;i<n;i++)
p[num][i]=a[i];
num++;
return;
}
else
{
for(i=start;i<n;i++)
{
swap(a[i],a[start]);
perm(a,start+1,n);
swap(a[i],a[start]);
}
}
}
//剩余排列数p[x][m]加到a[n]=0中
void add(int a[],int n,int x)
{
int i=0,j=0;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=p[x][j];
j++;
}
}
}
//计算是否k个 ,若是count++
void cou(int a[],int n,int k)
{
int i,j,c=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
c++;
}
if(c==k)
count++;
}
int main()
{
int n,k,m,i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
int a[n],b[n],c[n];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=i+1;
}
m=less(a,b,n);
perm(b,0,m);
for(i=0;i<num;i++)
{
for(j=0;j<n;j++)
c[j]=a[j];
add(c,n,i);
cou(c,n,k);
}
printf("%d\n",count);
count=0;
num=0;
}
}
