ACM_ICPC/Problems/6537

#include <stdio.h>

long long output = 0;
int outputcase[101];
void foo(int);
void foo2(int, int, int*, int*);

int main() {
	int T, n, k;
	int a[100];

	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		output = 0;
		foo(i);
	}
	for (int i = 0; i < T; i++) {
		printf("Case #%d: %d\n", i + 1, outputcase[i + 1]);
	}
}

void foo(int casenum) {
	int n, k;
	int a[101], temp[101];

	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d", &a[i]);
	}

	/* 초기화 */
	for (int i = 1; i <= n; i++) {
		temp[i] = 0;
	}
	for (int i = 1; i <= k; i++) {
		temp[a[i]] = 1;
	}

	foo2(n, k + 1, a, temp);

	outputcase[casenum + 1] = output;
}

void foo2(int n, int i, int a[101], int temp[101]) {
	if (i == n + 1) {
		int p = 0, g = 0;
		int b[101];

		for (int j = 1; j <= n; j++) {
			b[j] = a[j];
		}
		for (int j = 1; j <= n; j++) {
			if (j - b[j] > 0) {
				g += (j - b[j]);
			}
		}
		for (int j = 0; j < n - 1; j++) {
			for (int k = 1; k <= n - 1 - j; k++) {
				if (b[k] > b[k + 1]) {
					int temp = b[k];
					b[k] = b[k + 1];
					b[k + 1] = temp;
					p++;
				}
			}
		}
		if (p == g) {
			output++;
			if (output == 1000000007) {
				output = 0;
			}
		}

	}
	for (int j = 1; j <= n; j++) {
		if (temp[j] == 1) { continue; }
		a[i] = j;
		temp[j] = 1;
		foo2(n, i+1, a, temp);
		temp[j] = 0;
	}
}