Submission #545930

#	Time	Username	Problem	Language	Result	Execution time	Memory
545930		rainboy	Amusement Park (CEOI19_amusementpark)	C11	100 / 100	300 ms	59892 KiB

amusementpark

/* https://codeforces.com/blog/entry/68748?#comment-530893 (Paulliant) */
#include <stdio.h>

#define N	18
#define MD	998244353
#define MD2	996491788296388609LL
#define V2	499122177

void sub(int *aa, int n) {
	int i, b;

	for (i = 0; i < n; i++)
		for (b = 0; b < 1 << n; b++)
			if ((b & 1 << i) != 0 && (aa[b] += aa[b ^ 1 << i]) >= MD)
				aa[b] -= MD;
}

int main() {
	static int adj[N], cnt[1 << N], dp[N + 1][1 << N];
	static long long dq[N + 1][1 << N];
	int n, m, h, i, j, k, l, b, c;
	long long ans;

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		adj[i] |= 1 << j, adj[j] |= 1 << i;
	}
	for (b = 1; b < 1 << n; b++)
		cnt[b] = cnt[b & b - 1] + 1;
	for (b = 1; b < 1 << n; b++) {
		c = 0;
		for (i = 0; i < n; i++)
			if ((b & 1 << i) != 0)
				c |= adj[i];
		if ((b & c) != 0)
			continue;
		dp[cnt[b]][b] = cnt[b] % 2 == 0 ? MD - 1 : 1;
	}
	for (k = 0; k <= n; k++)
		sub(dp[k], n);
	for (b = 0; b < 1 << n; b++)
		dq[0][b] = 1;
	for (k = 0; k < n; k++) {
		for (b = 0; b < 1 << n; b++)
			dq[k][b] %= MD;
		for (l = 1; k + l <= n; l++)
			for (b = 0; b < 1 << n; b++)
				if ((dq[k + l][b] += dq[k][b] * dp[l][b]) >= MD2)
					dq[k + l][b] -= MD2;
	}
	ans = 0;
	for (b = 0; b < 1 << n; b++)
		ans += dq[k][b] % MD * (cnt[(1 << n) - 1 ^ b] % 2 == 0 ? 1 : -1);
	ans %= MD;
	if (ans < 0)
		ans += MD;
	ans = ans * m % MD * V2 % MD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

amusementpark.c: In function 'main':
amusementpark.c:30:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |   cnt[b] = cnt[b & b - 1] + 1;
      |                    ~~^~~
amusementpark.c:54:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   54 |   ans += dq[k][b] % MD * (cnt[(1 << n) - 1 ^ b] % 2 == 0 ? 1 : -1);
      |                               ~~~~~~~~~^~~
amusementpark.c:24:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
amusementpark.c:26:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37