【hdu5304】스패닝 트리 수 - 키르호프 매트릭스 DP

무방향도를 주고 몇 개의 자도가 기환수인지 구해라.
매거환 후 축점, 다시 살아서 나무 계수를 구한다.
2^n 매거링의 점, dp는 매 집합의 링의 개수를 미리 처리한다(기본값은 번호가 가장 작은 점을 기점으로 한다). f[i][s]로 링의 끝을 i로 표시하고 점 집합을 s로 한다.

#include 
#include 
#include 
#include 
#include 
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex)
using namespace std;
typedef long long LL;
const int N = 18, mod = 998244353, S = (1 << 17) + 2;
int n, m, nx, d[N][N], c[N], l;
LL a[N][N], ans, f[N][S];
LL Pow(LL x, LL y) {
	if (x < 0) x += mod;
	LL z = 1;
	while (y) {
		if (y & 1) z = z * x % mod;
		x = x * x % mod, y >>= 1;
	}
	return z;
}
LL Gauss() {
	int fl = 1;
	Rep(i, 1, l) {
		Rep(j, i, l) if (a[j][i]) {
			if (i != j) fl *= -1;
			Rep(k, 1, l) swap(a[i][k], a[j][k]);
			break ;
		}
		if (!a[i][i]) return 0;
		LL tp = Pow(a[i][i], mod - 2);
		Rep(j, i + 1, l) if (a[j][i]) {
			LL z = a[j][i] * tp % mod;
			Rep(k, 1, l) a[j][k] = (a[j][k] - (z * a[i][k] % mod) + mod) % mod;
		}
	}
	LL s = fl;
	Rep(i, 1, l) s = (s * a[i][i]) % mod;
	return (s + mod) % mod;
}
int main()
{
	while (scanf ("%d%d", &n, &m) != EOF) {
		nx = 1 << n; ans = 0;
		memset(d, 0, sizeof(d));
		Rep(i, 1, n) Rep(j, 0, nx) f[i][j] = 0;
		Rep(i, 1, m) {
			int x, y;
			scanf ("%d%d", &x, &y);
			d[x][y] = d[y][x] = 1;
		}
		Rep(i, 1, n) {
			f[i][1 << i-1] = 1;
			Rep(s, (1 << i-1), nx - 1) if ((((1 << i-1) - 1) & s) == 0){
				Rep(j, i, n) if (f[j][s]) {
					Rep(k, i + 1, n) if ((s & (1 << k-1)) == 0 && d[j][k]) {
						(f[k][s + (1 << k-1)] += f[j][s]) %= mod;
					}
				}
			}
		}
		Rep(s, 1, nx - 1) {
			Rep(i, 1, n) Rep(j, 1, n) a[i][j] = 0;
			int k; LL sc = 0;
			Rep(i, 0, n - 1) if ((1 << i) & s) { k = i + 1; break ; }
			c[k] = l = 1;
			Rep(i, k + 1, n) if ((1 << i-1) & s) {
				(sc += f[i][s] * d[i][k]) %= mod;
				c[i] = 1;
			}
			Rep(i, 1, n) if (!((1 << i-1) & s)) c[i] = ++ l;
			if (n - l < 2) continue ;
			Rep(i, 1, n) {
				Rep(j, i + 1, n) if (d[i][j]) {
					int x = c[i], y = c[j];
					a[x][y] --, a[y][x] --, a[x][x] ++, a[y][y] ++;
				}
			}
			l --;
			(ans += (Gauss() * sc % mod) * Pow(2, mod - 2)) %= mod;
		}
		printf ("%I64d
", ans);
	}

	return 0;
}