結果

問題 No.2384 Permutations of Permutations
コンテスト
ユーザー 👑 ygussany
提出日時 2023-07-16 12:33:29
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,930 bytes
コンパイル時間 417 ms
コンパイル使用メモリ 34,420 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-17 12:42:11
合計ジャッジ時間 1,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Mod = 998244353;
long long fact[100001], fact_inv[100001];

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

long long combination(int n, int k)
{
	if (k < 0 || n < k) return 0;
	return fact[n] * fact_inv[k] % Mod * fact_inv[n-k] % Mod;
}

int perm[720][6], code[6][6][6][6][6][6], inv[720];

int composition(int f, int g)
{
	int i;
	static int p[6];
	for (i = 0; i < 6; i++) p[i] = perm[g][perm[f][i]];
	return code[p[0]][p[1]][p[2]][p[3]][p[4]][p[5]];
}

int is_automorphism(int F[])
{
	int i, j;
	for (i = 0; i < 720; i++) {
		for (j = 0; j < 720; j++) {
			if (F[composition(i, j)] != composition(F[i], F[j])) return 0;
		}
	}
	return 1;
}

int is_valid(int K, int F[])
{
	if (is_automorphism(F) == 0) return 0;
	
	int i, j, k;
	for (i = 0; i < 720; i++) {
		for (j = 0; j < K; j++) if (perm[i][j] != j + 1) break;
		if (j == K) {
			if (perm[i][j] != 0) continue;
			for (j = K + 1; j < 6; j++) if (perm[i][j] != j) break;
			if (j == 6) break;
		}
	}
	k = F[i];
	for (j = 0; j < K; j++) if (perm[k][j] != j + 1) break;
	if (j == K) {
		if (perm[k][j] != 0) return 0;
		else return 1;
	} else return 0;
}

int solve6(int K)
{
	int i, j, k = 0, p[6] = {0, 1, 2, 3, 4, 5}, pp[6] = {}, s[5], ss[5];
	while (1) {
		for (i = 0; i < 6; i++) perm[k][i] = p[i];
		code[p[0]][p[1]][p[2]][p[3]][p[4]][p[5]] = k;
		if (p[0] == 1 && p[1] == 0 && p[2] == 2 && p[3] == 3 && p[4] == 4 && p[5] == 5) s[0] = k;
		if (p[0] == 0 && p[1] == 2 && p[2] == 1 && p[3] == 3 && p[4] == 4 && p[5] == 5) s[1] = k;
		if (p[0] == 0 && p[1] == 1 && p[2] == 3 && p[3] == 2 && p[4] == 4 && p[5] == 5) s[2] = k;
		if (p[0] == 0 && p[1] == 1 && p[2] == 2 && p[3] == 4 && p[4] == 3 && p[5] == 5) s[3] = k;
		if (p[0] == 0 && p[1] == 1 && p[2] == 2 && p[3] == 3 && p[4] == 5 && p[5] == 4) s[4] = k;
		if (p[0] == 1 && p[1] == 0 && p[2] == 3 && p[3] == 2 && p[4] == 5 && p[5] == 4) ss[0] = k;
		if (p[0] == 5 && p[1] == 3 && p[2] == 4 && p[3] == 1 && p[4] == 2 && p[5] == 0) ss[1] = k;
		if (p[0] == 3 && p[1] == 2 && p[2] == 1 && p[3] == 0 && p[4] == 5 && p[5] == 4) ss[2] = k;
		if (p[0] == 5 && p[1] == 4 && p[2] == 3 && p[3] == 2 && p[4] == 1 && p[5] == 0) ss[3] = k;
		if (p[0] == 2 && p[1] == 3 && p[2] == 0 && p[3] == 1 && p[4] == 5 && p[5] == 4) ss[4] = k;
		
		for (i = 5, pp[p[5]]++; i > 0; i--) {
			pp[p[i-1]]++;
			if (p[i] > p[i-1]) break;
		}
		if (i == 0) break;
		k++;
		for (i--, j = p[i] + 1; pp[j] == 0; j++);
		p[i] = j;
		pp[j]--;
		for (i++, j = 0; i < 6; i++) {
			while (pp[j] == 0) j++;
			p[i] = j;
			pp[j]--;
		}
	}
	
	int F[720], q[720], head, tail = 0;
	for (i = 0; i < 720; i++) F[i] = -1;
	F[0] = 0;
	q[tail++] = 0;
	for (head = 0; head < tail; head++) {
		i = q[head];
		for (j = 0; j < 5; j++) {
			k = composition(s[j], i);
			if (F[k] < 0) {
				F[k] = composition(ss[j], F[i]);
				q[tail++] = k;
			}
		}
	}
	
	int G[720], H[720], ans = 0;
	for (i = 0; i < 720; i++) {
		for (j = 0; j < 720; j++) if (composition(i, j) == 0) break;
		inv[i] = j;
	}
	for (i = 0; i < 720; i++) {
		for (j = 0; j < 720; j++) G[j] = composition(i, composition(j, inv[i]));
		for (j = 0; j < 720; j++) H[j] = G[F[j]];
		ans += is_valid(K - 1, G) + is_valid(K - 1, H);
	}
	return ans;
}

int main()
{
	int N, K;
	scanf("%d %d", &N, &K);
	
	int i;
	for (i = 1, fact[0] = 1; i <= N; i++) fact[i] = fact[i-1] * i % Mod;
	for (i = N - 1, fact_inv[N] = div_mod(1, fact[N], Mod); i >= 0; i--) fact_inv[i] = fact_inv[i+1] * (i + 1) % Mod;
	if (N == 2) printf("1\n");
	else if (N != 6) printf("%lld\n", K * fact[N-K] % Mod);
	else {
		// printf("%d\n", solve6(K));
		switch (K) {
		case 2:
			printf("192\n");
			break;
		case 3:
			printf("54\n");
			break;
		case 4:
			printf("16\n");
			break;
		case 5:
			printf("10\n");
			break;
		case 6:
			printf("6\n");
			break;
		}
	}
	fflush(stdout);
	return 0;
}
0