Pólya计数训练

选择部分非模板 Pólya 定理练习题。

POJ2154

题意：

用 \(n\) 种颜色给长为 \(n\) 的项链染色，旋转后相同算一种方案，求本质不同方案数。

思路：

将点从 0 开始编号。

显然旋转群一共有 \(n\) 个置换，也就是 \(p_i=(i+j)\bmod n\) ，其中 \(j=0,1,\cdots ,n-1\) 。

分析一下第 \(j\) 个置换形成的有向图，从 \(i\) 号点出发，每次步长为 \(j\) ，因为该图为若干个环，所以一定会回到 \(i\) 号点， 即 \(i=(i+kj)\bmod n\) ，\(n|kj\) ，满足条件的最小的正整数 \(k\) 为 \(lcm(n,j)/j=n/gcd(n,j)\) 。

也就说每个点都处于一个长为 \(n/gcd(n,j)\) 的环，环的个数为 \(gcd(n,j)\) 。

于是旋转群 \(G\) 的循环指标为：

\[P_G=\frac{1}{n}\sum_{j=0}^{n-1}x^{gcd(n,j)}_{n/gcd(n,j)}=\frac{1}{n}\sum_{d=0}^{n-1}\sum_{j=0}^{n-1}x^d_{n/d}[gcd(j,n)==d] =\frac{1}{n}\sum_{d|n}\sum_{j=0}^{\lfloor (n-1)/d \rfloor}x^d_{n/d}[gcd(j,n/d)==1] =\frac{1}{n}\sum_{d|n}\phi (n/d)x^d_{n/d}\]

带入计算即可，时间复杂度为 \(O(\sqrt{n})\) 。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
int n, mod;
vector<pair<int, int>>d;
ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
int ans;

void dfs(int i, int res, int phi)
{
    if (i == d.size()) {

        ans = (ans + phi * qmi(n, n / res - 1)) % mod;
        return;
    }
    dfs(i + 1, res, phi);

    for (int _ = 1; _ <= d[i].second; _++)
    {

        res *= d[i].first;
        if (_ == 1)phi *= (d[i].first - 1);
        else phi *= d[i].first;

        dfs(i + 1, res, phi);

    }

}

void solve()
{
    cin >> n >> mod;
    d.clear(), ans = 0;
    int m = n;
    for (int i = 2; i <= m / i; i++)
    {
        if (m % i == 0) {
            int cnt = 0;
            while (m % i == 0)cnt++, m /= i;
            d.emplace_back(i, cnt);
        }
    }
    if (m > 1)d.emplace_back(m, 1);
    //cout << d.size() << endl;
    dfs(0, 1, 1);
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

CF2040F

题意：

给长方体每个单位立方体染色，对长方体三个维度做任意次数的循环移位后相同的方案视为同一种，限制某种颜色使用次数，求本质不同方案。

分析：

类似于上一道题的分析，只是置换需要用 3 个维度的循环移位参数 \(i\) ，\(j\) ，\(k\) 来刻画。点 \((x,y,z)\) 走 \(t\) 步后到 \(((x+it)\bmod a,(y+jt)\bmod b,(z+kt)\bmod c)\) 。

即使是三个维度，最终还是会走到起点，同上一道分析可知 \(\frac{a}{gcd(i,a)}|t,\frac{b}{gcd(j,b)}|t,\frac{c}{gcd(k,c)}|t\) 。

于是 \(t\) 的最小正整数解为 \(lcm(\frac{a}{gcd(i,a)},\frac{b}{gcd(j,b)},\frac{c}{gcd(k,c)})\) 。

因为限制了颜色数量，不能直接用 Pólya 定理，但是可以考虑 Burnside 定理来计算每种置换作用下的染色不变量。 也就是要求每个置换环染上同一种颜色的方案数。

于是有了一个暴力做法，\(O(abc)\) 枚举所有置换，计算环长 \(t\) ，和环的个数 \(n/t\) ，因为题目限制 \(\sum_{i=1}^k d_i=abc\) ，也就是所有颜色给的所有单位立方体都要用上。 所以存在合法方案要求 \(d_i \bmod t = 0\) 对所有 \(i\) 成立，在这个条件成立下合法方案数就是多重集合的排列计数，即 \(\frac{(n/t)!}{\prod_{i=1}^{k} (d_i/t)!}\) 。

其实核心思路到这里也就差不多了，因为题目只限制了 \(\sum k\) 而没有限制 \(\sum abc\)，所以剩下的就是一些优化方法：

• 记 \(cnt[i]\) 表示环长为 \(i\) 的置换数，把相同环长放一起计算，并乘上 \(cnt[i]\) 的倍率，因为环长一定是 \(abc\) 的因子，这部分时间复杂度 \(O(d(abc)k)\) 。
• 对于 \(cnt\) 的计算，考虑到 \(\frac{a}{gcd(a,i)}\) 一定是 \(a\) 的因子，所以分别分解出 \(a\) ，\(b\) ，\(c\) 的因子，三重循环统计对 \(cnt\) 的贡献。具体的，因为满足 \(\frac{a}{gcd(i,a)}=u\) 和 \(0\leq i < a\) 的 \(i\) 有 \(\phi(u)\) 个，所以对环长 \(t=lcm(u,v,w)\) 的贡献为 \(\phi(u)\phi(v)\phi(w)\) ，这部分时间复杂度为 \(O(\sqrt{abc}+d(a)d(b)d(c))\) 。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 998244353;
const int N  = 3e6 + 10;

int fact[N], infact[N], d[N], cnt[N], phi[N];

ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
int a, b, c, k, n, g;
vector<int>p;
bool st[N];

void init()
{
    fact[0] = infact[0] = phi[1] = 1;
    for (int i = 1; i < N; i++)fact[i] = 1ll * i * fact[i - 1] % mod;
    infact[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i; i--)infact[i] = 1ll * (i + 1) * infact[i + 1] % mod;
    for (int i = 2; i <= N - 10; i++)
    {
        if (!st[i])p.push_back(i), phi[i] = i - 1;
        for (int j = 0; p[j] <= (N - 10) / i; j++)
        {
            st[p[j] * i] = 1;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
}

inline int calc(int x) {
    int res = 1;
    for (int i = 0; i < k; i++)res = 1ll * res * infact[d[i] / x] % mod;
    return 1ll * res * fact[n / x] % mod;
}

void solve()
{
    cin >> a >> b >> c >> k;
    n = g = a * b * c;

    auto get = [](int x, vector<int>&v)->void{
        for (int i = 1; i <= x / i; i++)
        {
            if (x % i == 0) {
                v.push_back(i);
                if (x / i != i)v.push_back(x / i);
            }
        }
    };

    vector<int>da, db, dc;

    get(a, da), get(b, db), get(c, dc);

    for (auto u : da)
        for (auto v : db)
            for (auto w : dc)
            {
                int len = lcm(u, lcm(v, w));
                cnt[len] += phi[u] * phi[v] * phi[w];
            }

    for (int i = 0; i < k; i++)cin >> d[i], g = __gcd(g, d[i]);

    int res = 0;
    for (int i = 1; i <= g; i++)
    {
        if (g % i == 0)
        {
            res = (res + 1ll * cnt[i] * calc(i)) % mod;
        }
    }
    cout << 1ll * res * qmi(n, mod - 2) % mod << '\n';
    for (auto u : da)
        for (auto v : db)
            for (auto w : dc)
            {
                int len = lcm(u, lcm(v, w));
                cnt[len] -= phi[u] * phi[v] * phi[w];
            }
}

int main()
{
    init();
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}