nn个珠子构成的环染mm种颜色, 并且规定一些颜色不能相邻. 旋转后相同算是同一种方案, 求本质不同的着色方案数

n109,m10n\le 10^9, m\le 10

POJ 2888

Solution

一道很好的Polya定理的题

  1. Burnside引理:对于一个置换ff,若一个染色方案ss经过置换后不变,称ssff的不动点。将ff的不动点数目记为C(f)C(f),则可以证明等价类数目为所有C(f)C(f)的平均值

  2. Polyta定理:假设一个置换有kk个循环,易知每个循环对应的所有位置颜色需一致,而任意两个循环之间选什么颜色互不影响。因此,如果有mm种可选颜色,则该置换对应的不动点个数为mkm^k。所以等价类数目为:i=0FmkiF\displaystyle \frac{\sum_{i=0}^{|F}m^{k_i}}{|F|}

    其中F|F|表示置换的数目,kik_i表示第ii个置换包含的循环个数

我们称把环旋转knπ\frac{k}{n}\cdot \pi度的置换为kk置换。显然k[0,n)k\in[0, n),即总共只有nn种置换,但本质不同的置换只有nn的约数种

这是因为,kk置换的循环长度为ngcd(k,n)\frac{n}{\gcd(k, n)},循环个数为gcd(k,n)\gcd(k, n)

想象一下在环上,一个点从11开始,每次往后跳kk步,最终跳回11号点所需要的步数,就是循环长度

根据Polya定理化式子:

ans=1ni=1nmgcd(n,i)=1ndnmdφ(nd) \begin{aligned} ans&=\frac{1}{n}\cdot \sum_{i=1}^{n}m^{gcd(n,i)}\\ &=\frac{1}{n}\cdot \sum_{d|n}\cdot m^{d}\cdot\varphi(\frac{n}{d}) \end{aligned}

枚举gcd(n,i)=d\gcd(n, i) = d,那么这样的ii会有φ(nd)\displaystyle \varphi(\frac{n}{d})个(ii要有dd这个因子,且把nnii同除dd后要互质)

式子中"mdm^d"部分即为,当gcd(n,i)=d\gcd(n, i) = d时不动点的个数。当没有限制时,这dd个循环每个都可以任选一种颜色

而这道题有颜色相邻的限制,所以需要预处理出fi,jf_{i, j}表示填了ii种颜色,第ii种颜色为jj的方案数。显然可以矩阵快速幂优化

一个小技巧:因为首尾也要满足条件,所以可以先多矩乘一次,然后把所有的Gi,iG_{i, i}相加即为答案

复杂度O(nm3logn)O(\sqrt n m^3\log n),跑不满

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Mod = 9973;
const int Maxn = 15;

int N, M, K;

namespace MATH
{
inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
return ans;
}

const int maxn = 1e5 + 100;

int prime[maxn], phi[maxn];
bool vis[maxn];

inline void init ()
{
int n = 1e5;
phi[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!vis[i]) prime[++prime[0]] = i, phi[i] = i - 1;
for (int j = 1; j <= prime[0] && (LL) i * prime[j] <= n; ++j)
{
vis[i * prime[j]] = 1;
if (!(i % prime[j]))
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}

inline int get_phi (int n)
{
if (n <= 1e5) return phi[n];
int ans = n;
for (int i = 1; prime[i] * prime[i] <= n; ++i)
if (!(n % prime[i]))
{
ans -= ans / prime[i];
while (!(n % prime[i])) n /= prime[i];
}
if (n > 1) ans -= ans / n;
return ans % Mod;
}
}

using namespace MATH;

struct mat
{
int A[Maxn][Maxn];
inline mat () { memset (A, 0, sizeof A); }

inline int* operator [] (const int &x) { return A[x]; }

inline mat operator * (const mat &rhs) const
{
mat now;
for (int i = 1; i <= M; ++i)
for (int k = 1; k <= M; ++k)
if (A[i][k])
for (int j = 1; j <= M; ++j)
Add (now.A[i][j], A[i][k] * rhs.A[k][j] % Mod);
return now;
}

inline mat operator ^ (int b)
{
mat ans, a = *this;
for (int i = 1; i <= M; ++i) ans.A[i][i] = 1;
for (int i = b; i; i >>= 1, a = a * a) if (i & 1) ans = ans * a;
return ans;
}

inline void init ()
{
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= M; ++j)
A[i][j] = 1;
}

inline void print ()
{
for (int i = 1; i <= M; ++i, puts(""))
for (int j = 1; j <= M; ++j)
cout << A[i][j] << " ";
}
} trans;

int ans;

inline void Calc (int x)
{
mat res = trans ^ x;
int sum = 0;
for (int i = 1; i <= M; ++i) Add (sum, res[i][i]);
sum = (LL) sum * get_phi (N / x) % Mod;
Add (ans, sum);
}

inline void Solve ()
{
ans = 0;
int m = sqrt (N);
for (int i = 1; i <= m; ++i)
if (!(N % i))
{
Calc (i);
if (i * i != N) Calc (N / i);
}
ans = (LL) ans * Pow (N, Mod - 2) % Mod;
printf("%d\n", ans);
}

inline void Input ()
{
N = read<int>(), M = read<int>(), K = read<int>();
trans.init ();
for (int i = 1; i <= K; ++i)
{
int x = read<int>(), y = read<int>();
trans[x][y] = trans[y][x] = 0;
}
}

int main()
{

#ifdef hk_cnyali
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
#endif

MATH :: init ();
int T = read<int>();
while (T--)
{
Input ();
Solve ();
}

return 0;
}