提出 #61906825


ソースコード 拡げる

// LUOGU_RID: 199590973
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
#pragma GCC target("avx")
using namespace std;

const int N = 30;
int n, mod, f[N][N][N * N], dp[2][N][N][N * N][N], ans[N * N];
// f(x, y, z) : 上一层 x 个点,下一层 y 个点,连 z 条边的方案数
// dp(a, b, c, d, e) : 该层奇偶性 a,b 个奇数层的点,c 个偶数层的点,d 条边,该层 e 个点 

inline void add(int &x, int y){
	x = (x + y < mod ? x + y : x + y - mod);
}

int c[N][N];
inline int C(int x, int y){
	return c[x][y];
}

signed main(){
	cin >> n >> mod;
	if (n & 1)	return puts("0"), 0;
	c[0][0] = 1;
	for (int i = 1; i <= n; i++){
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}
	for (int x = 1; x <= n / 2; x++){
		f[x][0][0] = 1;
		for (int y = 1; x + y <= n; y++)
			for (int z = 1; z <= n * (n - 1) / 2; z++)
				for (int l = 1; l <= min(z - y + 1, x + y - 1); l++)
					add(f[x][y][z], f[x][y - 1][z - l] * (C(x + y - 1, l) - C(y - 1, l) + mod) % mod);
	}
	dp[0][0][1][0][1] = 1;
	for (int i = 0; i < n - 1; i++){
		int cur = i % 2, nxt = (i + 1) % 2;
		memset(dp[nxt], 0, sizeof(dp[nxt]));
		for (int j = n - 1; j <= n * (n - 1) / 2; j++)
			for (int k = 1; k <= n / 2; k++)
				add(ans[j], dp[cur][n / 2][n / 2][j][k]);
		for (int x = 0; x <= n / 2; x++)
			for (int y = 0; y <= n / 2; y++)
				for (int j = 0; j <= n * (n - 1) / 2 - n + x + y; j++)
					for (int k = 1; k <= (cur ? x : y); k++)
						if (dp[cur][x][y][j][k]){
							for (int v = 1; v <= n / 2 - (nxt ? x : y); v++)
								for (int e = 1; e + j <= n * (n - 1) / 2 - (n - x - y - v) && e <= v * (v - 1) / 2 + v * k; e++){
									if (nxt)	add(dp[nxt][x + v][y][e + j][v], dp[cur][x][y][j][k] * C(n - x - y, v) % mod * f[k][v][e] % mod);
									else	add(dp[nxt][x][y + v][e + j][v], dp[cur][x][y][j][k] * C(n - x - y, v) % mod * f[k][v][e] % mod);
								}
						}
	}
	for (int j = n - 1; j <= n * (n - 1) / 2; j++)
		for (int k = 1; k <= n / 2; k++)
			add(ans[j], dp[(n - 1) % 2][n / 2][n / 2][j][k]);
	for (int i = n - 1; i <= n * (n - 1) / 2; i++)	cout << ans[i] << " " ;
	cout << endl;
	return 0;
}

提出情報

提出日時
問題 G - Odd Even Graph
ユーザ fwlqwq
言語 C++ 20 (gcc 12.2)
得点 0
コード長 2238 Byte
結果 WA
実行時間 1377 ms
メモリ 385660 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 600
結果
AC × 3
AC × 14
WA × 1
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 166 ms 383136 KiB
00_sample_01.txt AC 198 ms 383236 KiB
00_sample_02.txt AC 262 ms 383384 KiB
01_random_00.txt AC 76 ms 193380 KiB
01_random_01.txt AC 234 ms 383316 KiB
01_random_02.txt AC 296 ms 383492 KiB
01_random_03.txt AC 333 ms 383548 KiB
01_random_04.txt AC 366 ms 383704 KiB
01_random_05.txt AC 412 ms 383920 KiB
01_random_06.txt AC 463 ms 384196 KiB
01_random_07.txt AC 517 ms 384232 KiB
01_random_08.txt AC 621 ms 384624 KiB
01_random_09.txt AC 762 ms 384824 KiB
01_random_10.txt AC 996 ms 385316 KiB
01_random_11.txt WA 1377 ms 385660 KiB