Skip to Content
CTRL K

2019 - Amusement Park

Editorial de CF 

Pista

Podemos observar que para cada propuesta legal, invertir la dirección de sus aristas crea otra propuesta legal.

Los costos de estas dos propuestas serán mm porque cada arista se eligió una vez.

Así que la suma de costos será m⋅DAGCount2m\cdot\frac{\texttt{DAGCount}}2,

donde DAGCount\texttt{DAGCount} representa la cantidad de grafos dirigidos acíclicos (DAG) generados sobre el grafo original.

Explicación

Sea dp[S]\texttt{dp}[S] la cantidad de formas de construir un grafo dirigido acíclico (DAG) sobre el subgrafo inducido por el conjunto de vértices SS. Para cualquier DAG, al menos un vértice en SS debe tener grado de salida 0. Así,

dp[S]=∑∅≠P⊆S,P independent(# DAGs where P=the set of vertices with out-degree 0)=∑∅≠P⊆S,P independent(−1)∣P∣+1⋅(# DAGs where P⊆the set of vertices with out-degree 0)=∑∅≠P⊆S,P independent(−1)∣P∣+1⋅dp[S\P] \begin{aligned} \texttt{dp}[S] &= \sum_{\emptyset\neq P\subseteq S, P\text{ independent}}(\#\text{ DAGs where }P=\text{the set of vertices with out-degree 0})\\ &= \sum_{\emptyset\neq P\subseteq S, P\text{ independent}}(-1)^{|P|+1}\cdot (\#\text{ DAGs where }P\subseteq\text{the set of vertices with out-degree 0}) \\ &= \sum_{\emptyset\neq P\subseteq S, P\text{ independent}}(-1)^{|P|+1}\cdot \texttt{dp}[{S\backslash P}] \\ \end{aligned}

donde la segunda igualdad se sigue del principio de inclusión-exclusión  y de que todos los subconjuntos de un conjunto independiente también son independientes.

La complejidad temporal de enumerar subconjuntos es O(3n)\mathcal{O}(3^n).

Implementación

Complejidad temporal: O(3n)\mathcal{O}(3^n)

#include <cstring>
#include <iostream>
using namespace std;
const int N = 18;
const int M = 998244353;
int a[N];
bool indepset[1 << N];
int popcount[1 << N];
int arg[1 << N];
int nodeid[1 << N];
long long f[1 << N];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		a[u] |= 1 << v;
		a[v] |= 1 << u;
	}
	for (int i = 0; i < n; i++) { nodeid[1 << i] = i; }
	for (int i = 0; i < (1 << n); i++) {
		popcount[i] = popcount[i >> 1] + (i & 1);
		arg[i] = (popcount[i] % 2) * 2 - 1;
	}
	indepset[0] = 1;
	for (int i = 1; i < (1 << n); i++) {
		if (indepset[i & (i - 1)] && (a[nodeid[i & (-i)]] & (i & (i - 1))) == 0) {
			indepset[i] = true;
		}
	}
	f[0] = 1;
	for (int i = 1; i < (1 << n); i++) {
		for (int j = i; j; j = (j - 1) & i) {
			if (indepset[j]) { f[i] = (f[i] + arg[j] * f[i ^ j]) % M; }
		}
	}
	f[(1 << n) - 1] = (f[(1 << n) - 1] + M) % M;
	cout << f[(1 << n) - 1] * m % M * ((M + 1) / 2) % M;
	return 0;
}
Fundamentos