「考试总结」2023-02-13 联合省选模拟赛 – Day1

mqxmm · 2023-02-13 21:23:24 · 个人记录

\texttt {爆搜(dfs)}

\texttt {Statement}

给定一个 n 个点 m 条边的简单无向图，你需要对所有匹配 S ，把 c ^ { | S | } 求和，其中 | S | 是匹配的大小。对 10 ^ 9 + 7 取模。

一个匹配就是一个可以为空的边集，使得每个点至多是其中一条边的端点。

\texttt {Solution}

新增一个零度的点是不会对答案造成影响的，因此可以加点使 n 为偶数，并且默认点的标号为 0 \sim ( n - 1 ) 。

记匹配中的边为实边，在 点 2 i 和 点 2 i + 1 之间连一条虚边，得到新匹配。
因为 每个点至多是其中一条边的端点，所以连上虚边之后每个点的度数不超过 2 。
因此对于一个连通块，它只可能是一条链或者一个简单环。
那么对于新匹配，就是若干条链和若干个环组成的简单图。

显然新匹配和原匹配是一一对应的。
考虑在新匹配拆成若干个连通块 \texttt {dp} ，再把每个连通块拼起来。
一个连通块再分成链和环两种情况计算。

巧妙之处在于通过连虚边的方式转换问题，而新问题中 2i 和 2i + 1 一定是相连的，这样枚举点集的状态数就可以压缩至 2 ^ { 0.5 n } \leq 2 ^ {18} 个了，比纯 \texttt { dp } 优化了很多。

计算环的方法与 \texttt {「CF11D」A Simple Task} 类似，注意下 2i 和 2i + 1 是相连的即可。

这里只讲计算链的方法。

定义 f_{ s, i } 表示当前走过的点集为 s ，现在的终点为 i 的方案数。
枚举不在集合 s 中的点 j ，如果 i 和 j 之间实边相连，那么 f_{ t, j \texttt{ xor } 1 } \gets f_{ s, i } ，其中 t 表示 s 的集合中加入点 j 得到的新集合。 j \texttt { xor } 1 是因为点 j 与点 j \texttt { xor } 1 之间一定有边相连，判断的是 i 和 j ，新的终点就是 j \texttt { xor } 1 。

\texttt {Code}

#include <cstdio>

#define LL long long
#define uLL unsigned LL

namespace Read {
    static const int buf_size = 1 << 12;
    static const bool use_fread = true;

    static unsigned char buf[buf_size];
    static int buf_len, buf_pos;

    bool isEOF() {
        if (buf_pos == buf_len) {
            buf_pos = 0; buf_len = fread(buf, 1, buf_size, stdin);
            if (buf_pos == buf_len) return true;
        }
        return false;
    }

    char readChar() {
        if (!use_fread) return getchar();
        return isEOF() ? EOF : buf[buf_pos++];
    }

    LL rint() {
        LL x = 0, Fx = 1; char c = readChar();
        while (c < '0' || c > '9') { Fx ^= (c == '-'); c = readChar(); }
        while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = readChar(); }
        return Fx ? x : -x;
    }

    template <typename T>
    void read(T &x) {
        x = rint(); 
    }

    template <typename T, typename... Ts>
    void read(T &x, Ts &...rest) {
        read(x);
        read(rest...);
    }
} using namespace Read;

namespace Math {
    LL Max(LL u, LL v) { return (u > v) ? u : v; }
    LL Min(LL u, LL v) { return (u < v) ? u : v; }
} using namespace Math;

const int mod = 1e9 + 7;
const int inv = (mod + 1) >> 1;

const int MAX_n = 36;
const int MAX_m = 630;

const int mx = 1 << 18;

int n, m, c, up;

int qpow[MAX_n + 5];

int dp[mx + 5][MAX_n + 5];
int dpp[mx + 5][MAX_n + 5];

int dp1[mx + 5], dp2[mx + 5];

bool vis[MAX_n + 5][MAX_n + 5];

int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    read(n, m, c); n += (n & 1); up = 1 << (n >>= 1);
    for (int i = 1, u, v; i <= m; i++)
        read(u, v), --u, --v, vis[u][v] = vis[v][u] = true;
    qpow[0] = 1 % mod;
    for (int i = 1; i <= n; i++)
        qpow[i] = (LL)qpow[i - 1] * c % mod;
    for (int i = 0; i < n; i++) {
        dp[1 << i][i << 1] = dp[1 << i][i << 1 | 1] = 1;
        dpp[1 << i][i << 1 | 1] = 1;
    }
    for (int S = 1; S < up; S++) {
        int siz = 0, id = 0;
        for (int i = 0; i < n; i++)
            if (S & (1 << i)) ++siz;
        for (int i = 0; i < n; i++) {
            if (S & (1 << i)) {
                int a = i << 1, b = i << 1 | 1;
                for (int j = 0; j < n; j++) {
                    if (S & (1 << j)) continue;
                    int x = j << 1, y = j << 1 | 1, T = S | (1 << j);
                    if (vis[a][x]) dp[T][y] = (dp[T][y] + dp[S][a]) % mod;
                    if (vis[a][y]) dp[T][x] = (dp[T][x] + dp[S][a]) % mod;
                    if (vis[b][x]) dp[T][y] = (dp[T][y] + dp[S][b]) % mod;
                    if (vis[b][y]) dp[T][x] = (dp[T][x] + dp[S][b]) % mod;
                }
            }
        }
        for (int i = 0; i < n; i++)
            if (S & (1 << i)) { id = i; break; }
        for (int i = id; i < n; i++) {
            if (S & (1 << i)) {
                int a = i << 1, b = i << 1 | 1;
                for (int j = id + 1; j < n; j++) {
                    if (S & (1 << j)) continue;
                    int x = j << 1, y = j << 1 | 1, T = S | (1 << j);
                    if (vis[a][x]) dpp[T][y] = (dpp[T][y] + dpp[S][a]) % mod;
                    if (vis[a][y]) dpp[T][x] = (dpp[T][x] + dpp[S][a]) % mod;
                    if (vis[b][x]) dpp[T][y] = (dpp[T][y] + dpp[S][b]) % mod;
                    if (vis[b][y]) dpp[T][x] = (dpp[T][x] + dpp[S][b]) % mod;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            if (S & (1 << j)) {
                int x = j << 1, y = j << 1 | 1;
                dp1[S] = (dp1[S] + (LL)dp[S][x] * qpow[siz - 1] % mod * inv) % mod;
                dp1[S] = (dp1[S] + (LL)dp[S][y] * qpow[siz - 1] % mod * inv) % mod;
            }
        }
        for (int j = id; j < n; j++) {
            if (S & (1 << j)) {
                int x = j << 1, y = j << 1 | 1;
                if (vis[x][id << 1]) dp1[S] = (dp1[S] + (LL)dpp[S][x] * qpow[siz]) % mod;
                if (vis[y][id << 1]) dp1[S] = (dp1[S] + (LL)dpp[S][y] * qpow[siz]) % mod;
            }
        }
    }
    dp2[0] = 1 % mod;
    for (int S = 1; S < up; S++) {
        int siz = 0, id = 0;
        for (int i = 0; i < n; i++)
            if (S & (1 << i)) ++siz, id = i;
        for (int T = S; T & (1 << id); T = (S & (T - 1)))
            dp2[S] = (dp2[S] + (LL)dp2[S ^ T] * dp1[T]) % mod;
    }
    printf("%d\n", dp2[up - 1]);
    return 0;
}