UVA 11255 Necklace（每种颜色珠子个数限制、Polya原理、组合数）

题目链接：
UVA 11255 Necklace
题意：
各有$a,b,c(a,b,c \geq 0, a+b+c \leq 40)$颗三种颜色，问这些珠子能串成的项链有多少种?考虑翻转和旋转。
分析：
令$\sum_{i=1}^{3}color[i]=n$,即珠子总数。

• 考虑旋转置换。

我们考虑旋转$i$颗珠子的间距，则$0,i,2i...构成一个循环$，这个循环有$\frac{n}{gcd(n,i)}$.根据对成性，所有循环的长度均相同，因此一共有$gcd(i,n)$个循环。循环与循环之间是等价类，所以在一个循环内的某颗珠子的颜色确定了，那么在其余循环内的同样地位位置的珠子颜色也就确定了。我们得到的答案是每个循环的方案数并且在旋转置换下，当循环节确定了，每个循环的方案数都是一样的 。我们假设循环节的长度（也就是循环内元素的个数）为$x\in [0,n)$，第$i$种颜色的珠子的个数为$color[i]$个，如果$color[i] \% x !=0$,那么第$i$种颜色的珠子在每个循环（等价类）内就不能均分，所以这种循环节就应该摒弃。当$color[i] \% x ==0$时，令$b[i] = \frac{color[i]}{x}$，则$b[i]$就是每个循环（等价类）分得的这种颜色的珠子的个数。显然每个循环（等价类）内共有$\sum_{i=1}^{3}b[i]=\frac{1}{x}\sum_{i=1}^{3}color[i]$颗珠子，记为$sum$.我们考虑单个循环（等价类）：有$sum$颗珠子，各个颜色分别有$b[i]$颗，那么根据排列组合在循环节为$x$时，可得$Ans[x]=C_{sum}^{b[0]}*C_{sum-b[0]}^{b[1]}*C_{sum-b[0]-b[1]}^{b[2]}$.

• 考虑翻转置换

当$n$为奇数时，则对称轴上必有一点，对称轴有$n$条，每条对称轴形成$\frac{n-1}{2}$个长度为$2$的循环和$1$个长度为$1$的循环。
当$n$为偶数时，有两种对称轴。穿过珠子的对称轴有$\frac{n}{2}$条，各形成$\frac{n}{2}-1$个长度为2的循环和两个长度为$1$的循环。不穿过珠子的对称轴也有$\frac{n}{2}$条，各形成$\frac{n}{2}$个长度$2$的循环。

可以发现不论$n$为奇偶，对称轴的总个数都为$n$，同时旋转置换的个数也为$n$,所以根据$Burnside引理$最后需要除以$2n$.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 42;ll C[MAX_N][MAX_N];
int color[5], b[5], n;void init() //组合数打表
{C[0][0] = 1;for(int i = 1; i < MAX_N; ++i) {C[i][0] = C[i][i] = 1;for(int j = 1; j < i; ++j) {C[i][j] = C[i - 1][j] + C[i - 1][j - 1];}}
}int gcd(int x, int y)
{return y == 0 ? x : gcd(y, x % y);
}ll CircleSection(int x)
{int sum = 0;for(int i = 1; i <= 3; ++i) {if(b[i] % x) return 0;b[i] /= x;sum += b[i];}ll res = 1;for(int i = 1; i <= 3; ++i) {res *= C[sum][b[i]];sum -= b[i];}return res;
}ll Rotate() //旋转置换
{ll res = 0;for(int i = 0; i < n; ++i) {int d = gcd(i, n);memcpy(b, color, sizeof(color));res += CircleSection(n / d); //n/d是循环元素个数}return res;
}ll Flip() //翻转置换
{ll res = 0;if(n & 1) {for(int i = 1; i <= 3; ++i) {memcpy(b, color, sizeof(color));b[i]--; if(b[i] < 0) continue;res += CircleSection(2) * n; //n条对称轴}}else {//穿过珠子for(int i = 1; i <= 3; ++i) {for(int j = 1; j <= 3; ++j) {memcpy(b, color, sizeof(color));b[i]--, b[j]--;if(b[i] < 0 || b[j] < 0) continue;res += CircleSection(2) * (n / 2);}}//不穿过珠子memcpy(b, color, sizeof(color));res += CircleSection(2) * (n / 2);}return res;
}int main()
{init();int T;scanf("%d", &T);while(T--) {n = 0;for(int i = 1; i <= 3; ++i) {scanf("%d", color + i);n += color[i];}ll ans = 0;ans += Rotate();ans += Flip();printf("%lld\n", ans / (2 * n));}return 0;
}