[問題案] Enumerate Cliques

[SSRS-cp]

問題ID: enumerate_cliques 問題名: Enumerate Cliques

問題概要

N 頂点 M 辺の単純無向グラフが与えられる。各頂点に整数 x_i がある。 グラフのそれぞれのクリークに対し、属する頂点の x_i の積を求め、総和 mod 998244353 を出力せよ。

入力

#442 と同じ

出力

答えを出力

制約

1 <= N <= 100 1 <= M <= 100 0 <= x_i < 998244353 0 <= u_i < N 0 <= v_i < N u_i != v_i {u_i, v_i} != {u_j, v_j} (i != j)

メモ

計算量はたぶん O(2^√(2M)*N) です

出題例: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306

[SSRS-cp]

衝突確率の評価はしていないので、もっと良い答えさせ方があるかもしれません

[maspypy]

衝突確率

これは N/MOD 以下です。 https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

[yosupo06]

https://www.slideshare.net/wata_orz/ss-12131479 p15

[yosupo06]

よさそうです

[shirotsume4]

問題文は以下の通りでよいですかね？概ね enumerate triangles に則っています

$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられます。 $i$ 番目の辺は ${u_i, v_i }$ です。$G$ の各頂点 $i$ には整数 $x_i$ が割り当てられています。

$G$ のクリーク $C$ すべてに対する $\prod_{i \in C} x_i$ の総和を $998244353$ で割った余りを求めてください。