题意

一个无向图， $n$ 个点 $m$ 条边。

需要构造长度为 $d$ 的序列，要求必须包含 $[1,k]$ 的点，且相邻项有边连接，相邻不相同，可以重复。求序列数量。

$1\le n \le 20, 1 \le m \le \min(150,n*(n-1)/2),0 \le k \le \min(n,7),1\le d \le 10^9$ 。

题解

考虑 $k=0$ 的情况，发现直接矩乘维护即可。

然后 $k>0$ ，由于 $k\leq 7$ ，直接 $2^k\leq128$ 容斥即可。

代码

const int N = 25, mod = 1e9 + 9;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m, k, d;
	struct Matrix {
		int n, m;
		ll mat[N][N];
		ll* operator [](int pos) { return mat[pos]; }
		Matrix operator *(Matrix b) {
			Matrix c; c.n = n, c.m = b.m;
			memset (c.mat, 0, sizeof c.mat);
			for (int i = 1; i <= c.n; i++)
				for (int j = 1; j <= c.m; j++)
					for (int k = 1; k <= c.n; k++)
						(c[i][j] += mat[i][k] * b[k][j] % mod) %= mod;
			return c;
		}
	}G, org;

	Matrix qpow (Matrix a, ll b) {
		Matrix ans; ans.n = a.n, ans.m = a.m;
		memset (ans.mat, 0, sizeof ans.mat);
		for (int i = 1; i <= ans.n; i++) ans[i][i] = 1;
		for (; b; b >>= 1, a = a * a)
			if (b & 1) ans = ans * a;
		return ans;
	}

	int main () {
		n = Read(), m = Read(), k = Read(), d = Read();
		org.n = org.m = n;
		for (int i = 1; i <= m; i++) {
			int u = Read(), v = Read();
			org[u][v] = org[v][u] = 1;
		}
		ll ans = 0;
		for (int bit = 0; bit <= (1 << k) - 1; bit++) {
			G = org; int cnt = 0;
			for (int i = 1; i <= k; i++) {
				cnt += (bit >> i - 1) & 1;
				for (int j = 1; j <= n; j++) {
					G[j][i] &= (bit >> i - 1) & 1;
					G[i][j] &= (bit >> i - 1) & 1;
				}
			}
			G = qpow(G, d - 1);
			for (int i = 1; i <= n; i++) {
				if (i <= k && !((bit >> i - 1) & 1)) continue;
				for (int j = 1; j <= n; j++) {
					if (j <= k && !((bit >> j - 1) & 1)) continue;
					(ans += ((k - cnt) & 1)? mod-G[i][j]: G[i][j]) %= mod;
				}
			}
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	freopen("tourist.in", "r", stdin);
	freopen("tourist.out", "w", stdout);
	Main::main();
	return 0;
}