Yijan's Blog HomeArchives
Burnside 引理 & Polya 杂题

终于做了一些比 入门篇 难一些的题。

A AUOJ1600 礼物

其实是道板子+式子题。大概是 Burnside 引理的第一种题型（强行拼上去）。

image.png

我们考虑设 $f(a,b)$ 为 $a$ 个点形成环，从中选择 $b$ 个位置选中，且选中位置没有连续 $k$ 个的方案数量。

由于是循环同构，我们枚举置换再算环的个数，然后就可以得到和入门篇基本一样的式子，然后最后就是：

考虑怎么快速计算 $f(a,b)$ 。

我们先把 $a-b$ 个不选的棋子放好，然后将剩下的棋子插入进去。由于其实是一个环，我们考虑把首尾的棋子都放在开头，然后每个不选的棋子的前面放东西。注意到只有第一个棋子前面放东西会对方案造成其他影响，因为环的开头可以转，所以如果在第一个棋子前面放 $i$ 个棋子，会导致方案乘上 $(i+1)$ 。于是我们写成生成函数的形式：

我们设 $G(x) = \sum_{i=0}^{k-1} x^i$ ，而后面那个看起来很像一个求导的形式于是

然后：

最后要求的是 $[x^b]F(x)$ 。

注意到分母有值的只有 $O(\frac b k)$ 项，后面只有 $3$ 项，所以我们枚举这两个分别在哪一项，然后乘上剩下那个的 $b$ 减去之前两项的次数和。不难发现 $\frac 1 {(x-1)^{a-b+1}}$ 是个经典东西，插板一下得到 $[x^t] = \binom{t+a-b}{a-b}$ 。

于是就做完了，复杂度是 $O(\frac{\sigma_1(\gcd(n,m))}{k}) \approx O(\frac{n\log\log n}{k})$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n , m , k;
int A[MAXN];

int gcd( int a , int b ) {
	return !b ? a : gcd( b , a % b );
}

int pri[MAXN] , en , phi[MAXN];
void sieve( ) {
	phi[1] = 1;
	rep( i , 2 , MAXN - 1 ) {
		if( !pri[i] ) pri[++ en] = i , phi[i] = i - 1;
		for( int j = 1 ; j <= en && pri[j] * i < MAXN ; ++ j ) {
			pri[i * pri[j]] = 1;
			if( i % pri[j] == 0 ) {
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			}
			phi[i * pri[j]] = phi[i] * ( pri[j] - 1 );
		}
	}
}

int cs[4] , xs[4];

int J[MAXN] , iJ[MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int C( int a , int b ) {
	if( a < b || b < 0 ) return 0;
	return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

int f( int a , int b ) {
	if( a == b ) return a < k ? 1 : 0;
	int res = 0;
	rep( o , 0 , 2 ) {
		int rem = b - cs[o] , x = xs[o];
		rep( i , 0 , min( a - b - 1 , rem / k ) ) {
			int tx = C( a - b - 1 , i ) * 1ll * x % P;
			tx = ( i & 1 ) ? P - tx : tx;
			res = ( res + tx * 1ll * C( rem + a - b , a - b ) ) % P;
			rem -= k;
		}
	}
	return res;
}

void solve() {
	cin >> n >> m >> k;
	++ k;
	cs[0] = 0 , cs[1] = k , cs[2] = k + 1;
	xs[0] = 1 , xs[1] = P - ( k + 1 ) , xs[2] = k;
	int g = gcd( n , m ) , res = 0;
	for( int i = 1 ; i * i <= g ; ++ i ) if( g % i == 0 ) {
		res = ( res + f( n / i , m / i ) * 1ll * phi[i] ) % P;
		if( i * i != g )
			res = ( res + f( n / ( g / i ) , m / ( g / i ) ) * 1ll * phi[g / i] ) % P;
	}
	cout << res * 1ll * Pow( n , P - 2 ) % P << endl;
}

signed main() {
	sieve();
	J[0] = 1;
	rep( i , 1 , MAXN - 1 ) J[i] = J[i - 1] * 1ll * i % P;
	iJ[MAXN - 1] = Pow( J[MAXN - 1] , P - 2 );
	per( i , MAXN - 1 , 1 ) iJ[i - 1] = iJ[i] * 1ll * i % P;
    int T;cin >> T;while( T-- ) solve();
//    solve();
}

B codechef Adi and the Matrix

感觉这就是另外一类 Burnside 引理的题。这里置换不再是旋转一次到旋转 $n$ 次了。

不难发现这道题里面可以的置换是任何一个行排列以及一个任意列排列。然后 $(i,j)$ 在一个确定的置换转回自己显然需要 $i,j$ 分别所在的排列的环的长度的 $\text{lcm}$ 次，途中经过的每个点显然都与 $(i,j)$ 必须相等，因此对于任意一组行列排列 $P,Q$ ，对于一对环 $p,q$ ，这两个环涉及到的点有 $|p|\times |q|$ 个，每个真正的等价类的的大小是 $\text{lcm}(|p|,|q|)$ ，所以实际上对于这对环来说，能作为不动点的染色方案有 $2^{\gcd(|p|,|q|)}$ 种。

因此实际重要的是排列的环长，所以我们可以枚举一下无序划分（这是很小的）来统计方案。

我们考虑一个长度为 $n$ 的排列每种划分的方案数。我们设第 $i$ 种长度为 $a_i$ ，有 $b_i$ 个，那么方案就是可重排列再加上每个内部圆排列计数，是：

所以一种暴力做法就是枚举行排列的划分再枚举列排列的划分，对两两环长分别算 $2^{\gcd}$ 次方，最后乘上这个系数即可。但是显然这样是过不去的。

注意到 $n\times m \le 550$ 根据经典操作我们可以只枚举较小的一边的划分，也就是 $23$ 的划分，然后另一边由于加入一个环的权值可以通过较小部分的划分以及环长算出来，做一个 $dp$ 即可。

$23$ 的划分大概是 $6 \times 10^4$ ，后面那个 $dp$ 复杂度看起来就很小，所以可以过掉。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 999
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 7;
int n , m;
int A[MAXN];

int gcd( int a , int b ) {
	return !b ? a : gcd( b , a % b );
}

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int J[MAXN] , iJ[MAXN] , iv[MAXN] , p2[MAXN] , dp[MAXN][MAXN] , res;

vi pr;
void wkr( int x , int lim ) {
	if( x == 0 ) {
		int w = J[n];
		int las = 0 , cn = 0;
		for( int x : pr ) {
			w = w * 1ll * iv[x] % P;
			if( x != las ) w = w * 1ll * iJ[cn] % P , las = x , cn = 1;
			else ++ cn;
		}
		w = w * 1ll * iJ[cn] % P;
		mem( dp );
		dp[0][1] = 1;
		rep( j , 1 , m ) {
			rep( i , 0 , m ) {
				int ic = 1;
				int p = 1;
				for( int x : pr ) p = p * 1ll * p2[gcd( x , j )] % P;
				rep( k , 0 , ( m - i ) / j ) {
					dp[i + j * k][j + 1] = ( dp[i + j * k][j + 1] + dp[i][j] * 1ll * iJ[k] % P * ic ) % P;
					ic = ic * 1ll * iv[j] % P * p % P;
				}
			}
		}
//		cout << dp[2][2] << endl;
		res = ( res + dp[m][m + 1] * 1ll * w ) % P;
		return;
	}
	rep( k , lim , x ) 
		pr.pb( k ) , wkr( x - k , k ) , pr.pop_back();
}

void solve() {
	J[0] = iJ[0] = p2[0] = 1;
	rep( i , 1 , MAXN - 1 ) J[i] = J[i - 1] * 1ll * i % P , iv[i] = Pow( i , P - 2 ) , iJ[i] = iJ[i - 1] * 1ll * iv[i] % P , p2[i] = p2[i - 1] * 2 % P;
	cin >> n >> m;
	if( n > m ) swap( n , m );
	wkr( n , 1 );
	cout << res * 1ll * iJ[n] % P << endl; 
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

C P4727 [HNOI2009]图的同构计数

这个类似于上一个题。

我们可以直接看成对邻接矩阵染 $0,1$ ，这样就跟上一个题更像了。

由于需要做的是无向边染色，因此我们需要满足 $(i,j) = (j,i)$ 。在加上这个限制后，这个题和上个题就有了细微的差距，这个题中你只需要保证 $(i,j)$ 和 $(j,i)$ 有且仅有只有一个被染色即可。我们还是考虑如果确定了这个排列。

  • 如果 $i,j$ 不在同一个环里面。其实在你枚举了一对环 $p,q$ 的时候，相当于对所有 $(a,b),a\in p,b\in q$ 染色完成，所以其实需要的限制就是不会把 $(p,q),(q,p)$ 都枚举到。这个限制是非常简单的，就在枚举了划分后枚举划分时保证 $p < q$ 即可。
  • 如果 $i,j$ 在同一个环 $p$ 。这种情况会稍微阴间一点，由于有了限制，方案不再试 $2^{\gcd(|p|,|p|) = |p|}$ 了。我们把这个环画出来，以一种顺序（比如顺时针）作为正方向。我们令环上点对 $(i,j)$ 的距离为 $i \to j$ 在这种顺序需要跨过的边数。于是我们现在需要做的，就是仅在 $(i,j)$ 距离小于等于 $(j,i)$ 的时候统计方案。也就是说，原本这种情况下有 $|p|$ 个环，每个环分别含有点 $(i,i),(i,p_i),(i,p_{p_i}),\dots$ ，现在只有这里面的前一半了，只有 $\lfloor\frac{|p|}{2}\rfloor$ 个环。也就是说，方案数量变成了 $2^{\lfloor\frac{|p|}{2}\rfloor}$ 。

对这两种情况分别讨论。复杂度是 $O(p(n) n^2)$ ，实际上完全跑不到。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 999
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 997;
int n , m;
int A[MAXN];

int gcd( int a , int b ) {
	return !b ? a : gcd( b , a % b );
}

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int pn , as = 0 , iv[MAXN] , p2[MAXN] , J[MAXN];
vi pr;
void wkr( int x , int lim ) {
	if( x == 0 ) {
		int w = pn , tw = 0;
		int las = 0 , cn = 0;
		for( int x : pr ) {
			if( x != las ) w = w * iv[J[cn]] % P , las = x , cn = 1;
			else ++ cn;
		}
		w = w * iv[J[cn]] % P;
		for( int x : pr ) w = w * iv[x] % P , tw += x / 2;
		for( int i = 0 ; i < pr.size() ; ++ i ) 
			for( int j = 0 ; j < i ; ++ j ) 
				tw += gcd( pr[i] , pr[j] );
		as = ( as + w * p2[tw % ( P - 1 )] ) % P;
		return;
	}
	rep( k , lim , x ) 
		pr.pb( k ) , wkr( x - k , k ) , pr.pop_back();
}

void solve() {
	cin >> n;
	p2[0] = J[0] = pn = 1;
	rep( i , 1 , n ) pn = pn * i % P;
	rep( i , 1 , P - 1 ) iv[i] = Pow( i , P - 2 ) , p2[i] = p2[i - 1] * 2 % P , J[i] = J[i - 1] * i % P;
	wkr( n , 1 );
	cout << as * 1ll * iv[pn] % P << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

D 美术作业

先鸽着。

文章作者: yijan
文章链接: https://yijan.co/burnside-yin-li-and-polya-za-ti/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！