「Universal OJ」:#308「UNR #2」 UOJ 拯救计划 – 题解

主要思路

看到这个很小的模数就知道肯定是个 Trick 题，一定不会让你去跑一般图的（估计是 NPC）。

首先，我们可以设颜色未标号的、用了 \(i\) 种颜色的方案数为 \(f_i\)，那么答案就是：

\[ ans = \sum_{i = 1}^k f_i k^{\underline{i}} \]

发现这个东西在 \(i > 2\) 时就直接被模成了 \(0\)。我们只需要算 \(f_1, f_2\) 即可。其中 \(f_1 = [m = 0]\)。\(f_2\) 的方案数等价于二分图的双部染色的方案数。所以，我们跑一边二分图然后算 \(2^b\) 即可，\(b\) 是连通块次数。

代码

// UOJ308.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int T, n, m, k, head[MAX_N], current, col[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 2];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % 6;
        bas = 1LL * bas * bas % 6;
        tim >>= 1;
    }
    return ret;
}

bool dfs(int u, int c)
{
    col[u] = c;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (col[edges[i].to] == -1 && !dfs(edges[i].to, c ^ 1))
            return false;
        else if (col[edges[i].to] != -1 && col[edges[i].to] == c)
            return false;
    return true;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        memset(head, -1, sizeof(int) * (n + 10));
        memset(col, -1, sizeof(int) * (n + 10));
        current = 0;
        if (m == 0)
        {
            printf("%d\n", fpow(k, n));
            continue;
        }
        for (int i = 1, u, v; i <= m; i++)
            scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
        int acc = 2;
        bool flag = true;
        for (int i = 1; i <= n; i++)
            if (col[i] == -1)
                flag &= dfs(i, 0), acc = 2LL * acc % 6;
        if (!flag)
        {
            puts("0");
            continue;
        }
        printf("%lld\n", 1LL * k * acc % 6 * (k - 1) % 6);
    }
    return 0;
}