牛客2020跨年场 D 衔尾蛇

我们发现题目中有若干旋转置换。
而对于一共有n条蛇的环而言，本题对应的置换群由一个单位置换和n-1个旋转置换构成。
根据burnside引理

我们可以对于每个置换求出不变的颜色数进而求出答案。
对于单次确定三种蛇使用个数的情况，即代码中的cal(a, b, c)
复杂度是O((a+b+c)log(a+b+c))
当然，我们能发现gcd只有log个，能够通过反演进一步优化到亚线性。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

ll cc[20][20];

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll cal(ll a, ll b, ll c) {
        if (a + b + c == 0) return 0;
    ll res = cc[a + b + c][a] * cc[b + c][b]; //处理单位置换
    for (int i = 1; i < a + b + c; i++) { //处理旋转i个位置的旋转置换
        int g = gcd(i, a + b + c);
        int d = (a + b + c) / g;
        if (a % d == 0 && b % d == 0 && c % d == 0) {
            res += cc[g][a / d] * cc[g - a / d][b / d];
        }
    }
    return res / (a + b + c);
}

int main() {
    //freopen("0.txt", "r", stdin);
    cc[0][0] = 1;
    for (int i = 1; i < 20; i++) {
        cc[i][0] = 1;
        for (int j = 1; j < 20; j++) cc[i][j] = cc[i - 1][j - 1] + cc[i - 1][j];
    }
    ll a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    ll ans = 0;
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; k++) {
                ans += cal(i, j, k);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}