NULL.

每棵树插板法求所有染色+树内置换方案数, 放到环上.

考虑循环节, 令一个循环节上所有相邻的点比对, 如果不同构则这个置换环失效, 不计算.

一种合法情形背后的不动点贡献是循环节数$ \times \prod{sum}$, 刚才放到点上的值, 前循环节个数个做连乘积, 这是情况数, 每个可能都贡献循环节数个不动点, 贡献循环节数个置换操作.

Burnside除一下.

依然有点云里雾里, 貌似没读懂变量.

代码没调过不知道对不对.

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
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

const int maxn = 1e+5 + 5;

struct edge {
  int to, nxt;
}e[maxn];
int ptr, lnk[maxn];
int n, m, strat[maxn], out[maxn], inc[maxn];
int hsh[maxn], bkt[maxn];
vector<int> circ;

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}
inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % p;
    index >>= 1;
    base = base * base % p;
  }
  return ret;
}
inline ll C(int N, int M) {
  ll ret = 1;
  for (int i = 2; i <= M; ++i) ret = (ret * i) % mod;
  ret = quick_power(ret, mod - 2);
  for (int i = N; i > N - M; --i)
    ret = (ret * i) % mod;
  return ret;
}
typedef map<int, int>::iterator iter;
void dfs(int x) {
  static int base = 1233;
  static ll hs1 = 37ll;
  static ll hs2 = 43ll;
  map<int, int> cnt, val;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (inc[y]) continue;
    dfs(y);
    cnt[hsh[y]]++;
    val[hsh[y]] = strat[y];
  }
  hsh[x] = base; strat[x] = m;
  for (iter i = cnt.begin(); i != cnt.end(); ++i) {
    hsh[x] = (hsh[x] * hs1 + i->first * hs2 + i->second) % mod;
    strat[x] = (strat[x] * C(val[i->first] + i->second - 1, i->second)) % mod;
  }
  hsh[x] = (hsh[x] * hs1 + 8761) % mod;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &out[i]);
    add(out[i], i);
  }
  // replacable : findcircle
  int o = 1;
  for (int i = 1; i <= n; ++i) o = out[o];
  while (!inc[o]) {
    inc[o] = 1;
    circ.push_back(o);
    o = out[o];
  }
  int cirsize = circ.size();
  for (int i = 0; i < cirsize; ++i)
    dfs(circ[i]);
  for (int i = 1; i <= cirsize; ++i) {
    bkt[gcd(i, cirsize)]++;
  }
  ll tot = 0, stb = 0;
  for (int i = 0; i < cirsize; ++i) {
    if (!i || !(cirsize % i)) {
      int x = gcd(i, cirsize); ll t = bkt[x];
      bool sol = true;
      for (int j = 0; j < cirsize; ++j)
        if (hsh[j] != hsh[(j + i) % k]) {
          sol = false;
          break;
        }
      if (sol) {
        tot = (tot + t) % p;
        for (int j = 0; j < t; ++j) t = t * strat[cir[j]] % p;
        stb = (stb + t) % p;
      }
    }
  }
  tot = stb * quick_power(tot, mod - 2) % p;
  printf("%lld\n", tot); 
  return 0;
}