ARC062F Painting Graphs with AtCoDeer

发表于 | 分类于

Description

有一个\(n\)个点\(m\)条边的简单（即无重边无自环）无向图，现在有\(k\)种颜色，要求你给每条边染色。

然后你每次可以选择一个简单环，进行一次循环位移。如果一个染色方案能经过若干次该种操作来变成另一种染色方案，那么称这两种染色方案本质相同。

求有多少种不同的染色方案，答案对\(10^9+7\)取模。

\(1\le n\leq 50, 1\leq m, k\leq 100\)。

Solution

首先一件很显然的事情是，每个点双之间是互相独立的，也就是说最后的答案是所有点双的答案之积。所以先求一遍点双再说。

然后点双可以分为三种情况来考虑：

第一种：只有一条边的点双。这种很好处理，答案就是\(k\)。

第二种：只有一个简单环的点双。这个可以转化为一个序列染色，然后可以做若干次循环位移。假设序列（环）长\(l\)，那么做\(x\)次循环位移得到的置换的轮换数为\(\gcd(l, x)\)，套用一下Pólya定理就可以得到答案： \[ \frac{1}{l}\sum_{i = 0}^{l - 1}k^{\gcd(l, i)} \]

第三种：其他情况。这样的话一定会出现环套环的现象，可以证明这样可以凑出所有的置换。那么只要两种方案不同，那么他们一定会在某种颜色的使用次数上不同。所以问题就转化为了\(x_1 + x_2+\ldots+x_k = l\)（\(l\)为该点双中的边数，其中每个变量为自然数）的解的数量。这是一个经典的隔板法问题，答案为： \[ \binom{l + k - 1}{k - 1} \]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <stack>
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll fac[200005], ifac[200005];
void process() {
  int n = 200000;
  fac[0] = 1;
  for(int i = 1; i <= n; i ++) fac[i] = (ll)i * fac[i - 1] % ha;
  ifac[n] = inv(fac[n]);
  for(int i = n - 1; i >= 0; i --) ifac[i] = (ll(i + 1)) * ifac[i + 1] % ha;
}
ll C(int n, int m) {
  if(n < m) return 0;
  ll ret = fac[n] * ifac[n - m] % ha;
  ret = ret * ifac[m] % ha;
  return ret;
}

const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
  G[u].push_back(v);
}
void ins_edge(int u, int v) {
  add_edge(u, v); add_edge(v, u);
}

int n, m, k;
int bcnt = 0, clk = 0;
int pre[maxn], bccno[maxn];
int pn[maxm], en[maxm];
using pii = std::pair<int, int>;
int dfs(int x, int fa = -1) {
  static std::stack<pii> S;
  int lowu = pre[x] = ++ clk;
  for(int v : G[x]) {
    pii e = pii(x, v);
    if(!pre[v]) {
      S.push(e);
      int lowv = dfs(v, x);
      lowu = std::min(lowu, lowv);
      if(lowv >= pre[x]) {
        bcnt ++;
        pn[bcnt] = en[bcnt] = 0;
        while(true) {
          pii ee = S.top(); S.pop();
          int a = ee.first, b = ee.second;
          en[bcnt] ++;
          if(bccno[a] != bcnt) pn[bcnt] ++, bccno[a] = bcnt;
          if(bccno[b] != bcnt) pn[bcnt] ++, bccno[b] = bcnt;
          if(a == x && v == b) break;
        }
      }
    } else if(v != fa && pre[v] < pre[x]) {
      S.push(e);
      lowu = std::min(lowu, pre[v]);
    }
  }
  return lowu;
}
void calc_bcc() {
  for(int i = 1; i <= n; i ++) {
    if(!pre[i]) dfs(i);
  }
}

int gcd(int a, int b) {
  if(!b) return a;
  else return gcd(b, a % b);
}
ll calc(int x) {
  if(en[x] == 1) {
    return k;
  } else if(en[x] == pn[x]) {
    ll ret = 0;
    for(int i = 0; i < en[x]; i ++) {
      ret = (ret + pow_mod(k, gcd(i, en[x]))) % ha;
    }
    ret = ret * inv(en[x]) % ha;
    return ret;
  } else {
    return C(en[x] + k - 1, k - 1);
  }
}

int main() {
  process();
  scanf("%d%d%d", &n, &m, &k);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  calc_bcc();
  ll ans = 1LL;
  for(int i = 1; i <= bcnt; i ++) {
    ans = ans * calc(i) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}