发表文章

[最新] 【Polya定理】Gym - 101873B Buildings

bbbbswbq 2月前 2

Step1 Problem:

给你顶部和底部是正 m 边形的柱体,侧面是边长为 n 的正方形,有 c 种颜色,一个侧面有 n*n 个格子可以染色,总共有 m*n*n 个格子可以染色。
可以沿着侧面方向旋转,旋转前和旋转后染色样子一样,算同一种方案,求有多少种染色方案。

Step2 Ideas:

置换群:G;置换群中置换个数:|G|;
我们喜欢用 m 阶循环这种记号来表示 置换。
m 阶循环:相邻元素可以直接到达,第 m 个位置可以到达第 1 个位置。
例如:5 阶循环:(1 5 2 4 3),1->5->2->4->3->1…..,3->4->2->5->1->3…..

前置技能还有:
共轭类格式:1^(c1) 2^(c2) … (n)^(cn),其中 cn 代表 n 阶置换的个数。
k 不动置换类(Zk):包含 k 的置换阶为 1
等价类(Ek):k 的轨迹
重要定理:|Ek||Zk| = |G|

Burnside 引理:群 G 是在这 n 个对象上用 m 种颜色进行染色后的方案集合上的置换群
不同等价类个数:L = sum{c1(ai)} / |G|, 1 <= i <= |G|; 其中 ai 是第 i 个置换
因为 sum{Zj} = sum{c1(ai)}, 1 <= j <= n, 1 <= i <= |G|; 其中 n 是置换对象个数
不同等价类个数还可以等于:L = sum{Zi} / |G|, 1 <= i <= n;

Polya 定理:群 G 是作用在 n 个对象上的置换群
不同等价类个数:L = sum{m^c(ai)} / |G|, 1 <= i <= |G|; 其中 c(ai) 为置换 ai 的循环节数(有多少个循环),一个置换对象有 m 种不同情况

区别和联系:
Polya 定理的群 G 是作用在 n 个对象上的置换群,相应地,Burnside 定理中的群 G 是在这 n 个对象上用 m 种颜色进行染色后的方案集合上的置换群。
Burnside 的 ai 和 Polya 的 ai 是不一样的,但是都是求在 ai 置换之后不变的染色方案数的和 / |G|,因为每种染色情况都重复出现了 |G| 次
Burnside 的 ai 作用下不变的图像 正好是对应着 Polya 的 ai 的循环节中的对象染以相同的颜色所得到的图像,所以 c1(ai) = m^c(ai)

本题思路:
Polya 定理做法:
对于一个侧面有 k^(n*n) 种染色情况,也就是一个置换对象有 k^(n*n) 种不同的情况。
因为正 m 边形,所以共有旋转 0 个位置、1个位置、2个位置……旋转 m-1 个位置 等 m 种置换方法。
假设位置 0 到 m-1.
对于旋转 k 个位置这种置换:第 pos 个位置 和 第 (pos+k*t)%m 个位置一样, t >= 0.
pos+gcd(k, m)*t1,其中 0 <= pos+gcd(k, m)*t1 < m,代表我们能到达的所有位置。
每一个轨迹中位置的个数 t = m/gcd(k, m)。由于在本题中不同轨迹中的位置的个数相同,所以轨迹的个数就是 m/t = gcd(k, m)。因此,旋转 k 个位置之后和原来相同的染色方案数就是 (k^(n*n))^gcd(k, m)

Step3 Code:

//Polya做法:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9+7;
ll Pow(ll x, ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans *= x, ans %= MOD;
        x = x*x, x %= MOD;
        n >>= 1;
    }
    return ans;
}
int main()
{
    int n, m, c;
    scanf("%d %d %d", &n, &m, &c);
    ll ans = 0;
    ll tmp = Pow(c, n*n);//置换对象有那些染色情况
    for(int i = 0; i < m; i++) //第 i 个置换,旋转 i 个位置
    {
        int g = __gcd(i, m);//第 i 个置换,pos位置可以移动到 pos+(gcd(i, m)的倍数)位置
        int t = m/g;//每一个轨迹阶的大小
        int num = m/t;//本题中不同轨迹阶的大小相同,所以轨迹的个数 m/t = gcd(k, m);
        // g = num;
        ans += Pow(tmp, num), ans %= MOD;
    }
    ans = ans*Pow(m, MOD-2);//除置换群的大小,因为每种情况,都重复计算了 m 次
    ans %= MOD;
    printf("%lld\n", ans);
    return 0;
}
相关推荐
最新评论 (0)
返回
发表文章
bbbbswbq
文章数
449
评论数
0
注册排名
659730