对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k] )步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

代码:

// =================================
//   author: memset0
//   date: 2019.03.15 19:06:46
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 7e5 + 10, M = 20, BIT = 1 << 14, mod = 998244353;
int p, n, m, ans, limit;
int bit[N], fac[N], ifac[N], f[BIT][M], g[BIT][M], h[M], G[M][M];

inline void Dec(int &a, int b) { a -= b; if (a < 0) a += mod; }
inline void Sub(int &a, int b) { a += b; if (a >= mod) a -= mod; }
inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
inline int sub(int a, int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a, int b) { return (ll)a * b - (ll)a * b / mod * mod; }
inline int C(int n, int m) { return mul(fac[n], mul(ifac[m], ifac[n - m])); }
inline int inv(int x) { return x < 2 ? 1 : mul(mod - mod / x, inv(mod % x)); }
inline int fpow(int a, int b) { int s = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) s = mul(s, a); return s; }

int w[N << 2], rev[N << 2];
inline void ntt(int *a, int lim) {
    for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
    for (int len = 1; len < lim; len <<= 1)
        for (int i = 0; i < lim; i += (len << 1))
            for (int j = 0; j < len; j++) {
                int x = a[i + j], y = mul(w[j + len], a[i + j + len]);
                a[i + j] = sub(x, y), a[i + j + len] = dec(x, y);
            }
}

inline std::vector <int> operator * (const std::vector <int> &f, const std::vector <int> &g) {
    static int a[N << 2], b[N << 2]; std::vector <int> h(f.size() + g.size() - 1);
    int lim = 1, k = 0, inv_lim; while (lim < h.size()) lim <<= 1, ++k;
    for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
    for (int i = 0; i < lim; i++) a[i] = i < f.size() ? f[i] : 0;
    for (int i = 0; i < lim; i++) b[i] = i < g.size() ? g[i] : 0;
    ntt(a, lim), ntt(b, lim), inv_lim = inv(lim);
    for (int i = 0; i < lim; i++) a[i] = mul(a[i], b[i]);
    std::reverse(a + 1, a + lim), ntt(a, lim);
    for (int i = 0; i < h.size(); i++) h[i] = mul(a[i], inv_lim);
    return h;
}

inline std::vector <int> fpow(std::vector <int> a, int b) {
    std::vector <int> s(1, 1);
    for (; b; b >>= 1, a = a * a) if (b & 1) s = s * a;
    return s;
}

void main() {
    read(p), read(n), read(m), limit = n * p + 1;
    for (int wn, len = 1; (len << 1) < (N << 2); len <<= 1) {
        wn = fpow(3, (mod - 1) / (len << 1)), w[len] = 1;
        for (int i = 1; i < len; i++) w[i + len] = mul(w[i + len - 1], wn);
    }
    for (int i = 1, u, v; i <= m; i++) read(u), read(v), G[u][v] = G[v][u] = 1;
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= n * p; i++) fac[i] = mul(fac[i - 1], i);
    for (int i = 2; i <= n * p; i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
    for (int i = 2; i <= n * p; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
    for (int i = 1; i <= n; i++) f[1 << (i - 1)][i] = 1;
    for (int x = 0; x < (1 << n); x++) {
        for (int u = 1; u <= n; u++) if (f[x][u] && ((x >> (u - 1)) & 1))
            for (int v = 1; v <= n; v++) if (!G[u][v] && !((x >> (v - 1)) & 1))
                Sub(f[x | (1 << (v - 1))][v], f[x][u]);
        for (int i = 1; i <= n; i++) Sub(f[x][0], f[x][i]);
        g[x][1] = f[x][0];
    }
    for (int x = 0, cnt; cnt = 0, x < (1 << n); x++) {
        for (int i = 0; i < n; i++) if (!((x >> i) & 1)) bit[cnt++] = i;
        for (int y = 0, z; z = x, y < (1 << cnt); y++) {
            for (int i = 0; i < cnt; i++) if ((y >> i) & 1) z |= 1 << bit[i];
            for (int i = 1; i < n; i++) Sub(g[z][i + 1], mul(g[x][i], f[z ^ x][0]));
        }
    }
    for (int i = 1; i <= n; i++) h[i] = g[(1 << n) - 1][i];
    std::vector <int> a(n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            Sub(a[j], mul(h[i], mul((i - j) & 1 ? mod - 1 : 1, C(i - 1, j - 1))));
    for (int i = 1; i <= n; i++) a[i] = mul(a[i], ifac[i]);
    auto b = fpow(a, p);
    for (int i = 1; i < limit; i++) Sub(ans, mul(b[i], fac[i]));
    print(ans, '\n');
}

} signed main() { return ringo::main(), 0; }

生成函数 巧妙的思路 容斥 哈密顿回路