Chaos Slover 补档计划 - Burnside引理&Pólya定理

2015.11.13 08:31 Fri| 11 visits oi_2016| ChaosSlover补档计划| Text

Burnside 引理 & Pólya 定理

一听这名字就是很高级的定理啊 - -||

Burnside 引理

其中 L 表示互异的组合状态的个数,G={g1 ,…gs} 表示置换群,D(gj) 表示在置换 gj 下不变的元素的个数。

Pólya 定理

其中 c(gj) 为置换 gj 的循环节数。

可以借助这两个定理在一些情况下很方便地计算全部互异的组合状态的个数 。

BZOJ1004 [HNOI2008]Cards

题目中说,任意多次洗牌都可用这 m 种洗牌法中的一种代替,也就意味着题目中给出的就是 m 种置换方式,算上“不洗牌”共有 m+1 种置换。我们要计算出所有互异染色方案的个数,可以借助于 Burnside 引理(由于每种颜色的数目是固定的,不能利用 Pólya定理)。

利用 Burnside 引理,我们首先需要求出对于每一种置换的不变染色方案个数。对于置换 g,一个染色方案不变仅当它在 g 中的每一个循环上都染相同的颜色。这样我们就需要先求出每一个置换的循环个数和大小,为它们分别赋予一种颜色,使得最终用完全部三种颜色。这就是一个三维背包问题了。

最后不要忘记去除以置换的个数 m+1,这里需要用到逆元。

 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
#include <bits/stdc++.h>
using namespace std;

int sr, sb, sg, m, p, n, tot, ans, a[65], vis[65], cnt[65], f[65][25][25][25];

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

int main()
{
    cin >> sr >> sb >> sg >> m >> p;
    n = sr + sb + sg;
    for (int i = 0; i <= m; ++i)
    {
        if (i == 0)
        {
            tot = n;
            for (int i = 1; i <= n; ++i)
                cnt[i] = 1;
        }
        else
        {
            for (int j = 1; j <= n; ++j)
                scanf("%d", &a[j]);
            tot = 0;
            memset(vis, 0, sizeof vis);
            memset(cnt, 0, sizeof cnt);
            for (int i = 1, now = 1; i <= n; ++i)
                if (!vis[i])
                {
                    now = i; ++tot;
                    do
                        ++cnt[tot], vis[now] = 1, now = a[now];
                    while (now != i);
                }
        }
        memset(f, 0, sizeof f);
        f[0][0][0][0] = 1;
        for (int i = 1; i <= tot; ++i)
            for (int j = sr; j >= 0; --j)
                for (int k = sb; k >= 0; --k)
                    for (int l = sg; l >= 0; --l)
                    {
                        if (j >= cnt[i])
                            f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][j - cnt[i]][k][l]) % p;
                        if (k >= cnt[i])
                            f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][j][k - cnt[i]][l]) % p;
                        if (l >= cnt[i])
                            f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][j][k][l - cnt[i]]) % p;
                    }
        ans += f[tot][sr][sb][sg];
    }
    ans = ((ans * exgcd(m + 1, p).first % p) + p) % p;
    cout << ans << endl;
    return 0;
}

POJ2409 Let it Bead

题意:给出 c 种颜色去染一串长度为 s 的珠子。经过旋转或翻转可以变得相同的染色方案算作一种。问有多少种不同的染色方案。

考虑旋转和翻转,一共有 2*s 种置换,其中旋转 s 种,翻转 s 种。

首先考虑旋转。很显然,旋转 k*2π/s 度时,置换的循环有 gcd(k,s) 个。

翻转就要分 s 为奇数和偶数两种情况讨论了:

如果 s 为奇数的话,我们就会以每一个珠子到中心的连线作为对称轴进行翻转,有 (s+1)/2 个循环;

如果 s 为偶数的话,我们可能会以相对的两个珠子的连线作为对称轴进行翻转,有 s/2 种置换,每一种置换都含有 (s-2)/2+2 个循环;也可能以相对的两边的中点的连线作为对称轴,同样有 s/2 种置换,每一种置换都含有 s/2 个循环。

这时我们就可以很方便地用 Pólya 定理来进行统计了。

最后,题目限制 c*s <= 32,因此方案数会很少很少,只需要 int 就好了。

 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
#include <bits/stdc++.h>
using namespace std;

int c, s, ans;

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re *= a;
        a *= a; b >>= 1;
    }
    return re;
}

int main()
{
    while (cin >> c >> s, c || s)
    {
        ans = 0;
        for (int i = 1; i <= s; ++i)
            ans += power(c, __gcd(i, s));
        if (s & 1)
            ans += s * power(c, (s + 1) / 2);
        else
            ans += s / 2 * power(c, s / 2),
            ans += s / 2 * power(c, 2 + (s - 2) / 2);
        cout << ans / (s * 2) << endl;
    }
    return 0;
}

POJ1286 Necklace of Beads

和上一道题一模一样,无脑把 c 替换成 3,把 int 替换成 long long——然后就 RE 了。

然而发现我们需要特判 0——然后就 WA 了。因为当 n=0 时,答案竟然为 0!

UVA10733 The Colored Cubes

题意:给正方体的六个面染上 n 种颜色,问不同的方案数。

在正方体上的置换好麻烦的……很容易考虑漏情况。

  • 不变置换,含有 6 个循环,只有一种情况;
  • 以相对面的中轴线旋转 90° 或 270°,含有 3 个循环,共 6 种情况;
  • 以相对面的中轴线旋转 180°,含有 4 个循环,共 3 种情况;
  • 以对顶点的连线旋转 120° 或 240°,含有 2 个循环,共 8 种情况;
  • 以对边中点的连线旋转 180°,含有 3 个循环,共 6 种情况。 共计 24 种置换。
 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
#include <bits/stdc++.h>
using namespace std;

long long c, ans;

long long power(long long a, long long b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re *= a;
        a *= a; b >>= 1;
    }
    return re;
}

int main()
{
    while (cin >> c, c)
    {
        ans = power(c, 6);
        ans += 6 * power(c, 3);
        ans += 3 * power(c, 4);
        ans += 8 * power(c, 2);
        ans += 6 * power(c, 3);
        cout << ans / 24 << endl;
    }
    return 0;
}

UVA10601 Cubes

题意:给出12根小棒,每一根小棒都有一种颜色(颜色编号从 1 到 6),问能拼出来多少种不同的正方体。

结合 BZOJ1004 的做法,用 Burnside 引理加上【六维背包】求解。长方体上一共有 24 种置换,情况见上一道题,把面改成边细心地算一下就好了。不要问我的代码为什么如此难看。

另外这里开了一个很大的数组,然而其中绝大部分是完全不会被用上的。所以要用的时候在清零就好,如果经常清零会 TLE。

 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
#include <bits/stdc++.h>
using namespace std;

int t, c[7], tot, cnt[13], ans, f[13][13][13][13][13][13][13];

int main()
{
  cin >> t;
  while (t--)
  {
    memset(c, 0, sizeof c);
    for (int x, i = 1; i <= 12; ++i)
      scanf("%d", &x), ++c[x];
    ans = 0;
    for (int p = 1; p <= 5; ++p)
    {
      if (p == 1) {
        tot = 12;
        for (int i = 1; i <= 12; ++i) cnt[i] = 1;
      } else if (p == 2) {
        tot = 3;
        for (int i = 1; i <= 3; ++i) cnt[i] = 4;
      } else if (p == 3) {
        tot = 6;
        for (int i = 1; i <= 6; ++i) cnt[i] = 2;
      } else if (p == 4) {
        tot = 4;
        for (int i = 1; i <= 4; ++i) cnt[i] = 3;
      } else {
        tot = 7;
        cnt[1] = cnt[2] = 1;
        for (int i = 3; i <= 7; ++i) cnt[i] = 2;
      }
      f[0][0][0][0][0][0][0] = 1;
      for (int i = 1; i <= tot; ++i)
        for (int t1 = c[1]; t1 >= 0; --t1)
          for (int t2 = c[2]; t2 >= 0; --t2)
            for (int t3 = c[3]; t3 >= 0; --t3)
              for (int t4 = c[4]; t4 >= 0; --t4)
                for (int t5 = c[5]; t5 >= 0; --t5)
                  for (int t6 = c[6]; t6 >= 0; --t6)
                  {
                    f[i][t1][t2][t3][t4][t5][t6] = 0;
                    if (cnt[i] <= t1)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1 - cnt[i]][t2][t3][t4][t5][t6];
                    if (cnt[i] <= t2)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1][t2 - cnt[i]][t3][t4][t5][t6];
                    if (cnt[i] <= t3)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1][t2][t3 - cnt[i]][t4][t5][t6];
                    if (cnt[i] <= t4)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1][t2][t3][t4 - cnt[i]][t5][t6];
                    if (cnt[i] <= t5)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1][t2][t3][t4][t5 - cnt[i]][t6];
                    if (cnt[i] <= t6)
                      f[i][t1][t2][t3][t4][t5][t6] +=
                      f[i - 1][t1][t2][t3][t4][t5][t6 - cnt[i]];
                  }
      if (p == 1) {
        ans += f[tot][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]];
      } else if (p == 2) {
        ans += 6 * f[tot][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]];
      } else if (p == 3) {
        ans += 3 * f[tot][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]];
      } else if (p == 4) {
        ans += 8 * f[tot][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]];
      } else {
        ans += 6 * f[tot][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]];
      }
    }
    cout << ans / 24 << endl;
  }
  return 0;
}

// 这道题吓得我代码风格都变了。

// vjudge 是什么鬼东西,测了十分钟之后告诉我提交失败。

POJ2888 挖坑两天后再添

2016.10.22upd: 然而再也没有填