Description

给定一个长度为 $N$ 的排列，但是排列中某些位置的值被擦去了。

你想要还原这个排列，但是你唯一记得的信息是这个排列的逆序对个数为 $K$.

你想知道，有多少不同的还原方式，使得排列的逆序对数为 $K$.

一个排列的逆序对个数即满足 $i<j$, p_i > p_jpi>pj的$(i,j)$ 个数。

Input Format

第一行两个正整数 $N,K$.

接下来一行 $N$ 个整数 p_1,p_2,...p_Np1,p2,...pN, 如果 p_i=0pi=0 则表示这个位置的值被擦去了。

保证至少存在一个排列满足给定的格式。

Output Format

4 3
0 0 4 0

2

Hint

#include <stdio.h>
int N, K, p[17], vis[17], ans;
inline int count() {
	int i, j, result = 0;
	for(i = 1; i < N; i++)
		for(j = i+1; j <= N; j++)
			if(p[i] > p[j]) result++;
	return result;
}
void search(int depth) {
	if(depth == N+1) {
		ans = count() == K ? ans+1 : ans;
		return;
	}
	int i;
	if(p[depth]) search(depth+1);
	else {
		for(i = 1; i <= N; i++)
			if(!vis[i] && !p[depth]) {
				vis[i] = 1;
				p[depth] = i;
				search(depth+1);
				vis[i] = p[depth] = 0;
			}
	}
}
int main() {
	int i, cnt = 0;
	scanf("%d %d", &N, &K);
	for(i = 1; i <= N; i++) 
		scanf("%d", &p[i]);
	for(i = 1; i <= N; i++) {
		if(p[i]) vis[p[i]] = 1;
		else cnt++;
	}
	search(1);
	printf("%d\n", ans);
	return 0;
} 

Source