小米 OJ 编程比赛 01 月常规赛 C.星空 (置换群polya + 整数分拆)

Author Avatar
Sakits 1月 26, 2019

题解

  那天打比赛遇到这个题啃了半天才看懂题意…
  好久没做置换群了根本不会做…
  在ccz大爷的教导下才会了这题QAQ
  顺便复习了一波burnsidepolya
  首先显然有 n!n! 种置换,不动点个数只与轮换的组成有关,而且 nn 很小,所以考虑对 nn 做整数分拆,暴力求出所有轮换的方案,6060的分拆数是 9×1069\times 10^6左右,可以承受。
  连边相当于给邻接矩阵主对角线上方的 n×(n1)2\frac{n \times (n - 1)}{2} 个位置上色,有 k+1k + 1 种颜色可选。
  现在就是要求一个轮换方案里不动点的个数。考虑一个大小为 mm 的轮换内部连边,因为是双向边,所以连边的置换有 m2\frac{m}{2} 个循环节。两个大小分别为 m1,m2m_1, m_2 的轮换之间的边置换有 gcd(m1,m2)\gcd(m_1, m_2) 个循环节。至此可以得到总循环节数 cntcnt,那么一个这种轮换的置换不动点个数为 (k+1)cnt(k + 1) ^ {cnt},再乘上这种轮换方案的置换个数即可。这个算算就好了,懒得打公式了QAQ
  最后总不动点数除以 n!n! 就是等价类数了。
  辣鸡小米OJ一写递归gcd就爆栈

代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 65, inf = 1e9 + 233, mod = 2333;
int T, n, K, ans;
int cnt[maxn], b[maxn], fac[maxn], inv[maxn], a[maxn];

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

int gcd(int a, int b)
{
    int t;
    while (b) t = b, b = a % b, a = t;
    return a;
}

inline int power(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

inline void getans(int m)
{
    memset(cnt, 0, sizeof(cnt));

    int tott = 0;
    for (int i = 1; i <= m; i++) 
    {
        if (!cnt[b[i]]) a[++tott] = b[i];
        cnt[b[i]]++;
    }

    int mi = 0;
    for (int i = 1; i <= tott; i++)
    {
        mi += cnt[a[i]] * (a[i] >> 1);
        mi += (cnt[a[i]] * (cnt[a[i]] - 1) >> 1) * a[i];
        for (int j = i + 1; j <= tott; j++)
            mi += gcd(a[i], a[j]) * cnt[a[i]] * cnt[a[j]];
    }

    int sum = fac[n];
    for (int i = 1; i <= 60; i++)
        sum = sum * inv[cnt[i]] % mod * power(fac[i - 1] * inv[i] % mod, cnt[i]) % mod;

    // printf("mi:%d sum:%d\n", mi, sum);

    ans = (ans + sum * power(K + 1, mi)) % mod;
}

void dfs(int cnt, int dep, int pre)
{
    if (cnt == n) return (void)(getans(dep - 1));

    for (int i = pre; cnt + i <= n; i++)
    {
        b[dep] = i;
        dfs(cnt + i, dep + 1, i);
    }
}

int main()
{
    n = 60;
    fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[n] = power(fac[n], mod - 2); for(int i = n; i; i--) inv[i - 1] = inv[i] * i % mod;

    read(T);

    while (T--)
    {
        read(n); read(K);

        ans = 0;
        dfs(0, 1, 1);

        printf("%d ", ans * inv[n] % mod);
    }
}