首页 > 代码库 > uva 11255 - Necklace(置换)
uva 11255 - Necklace(置换)
题目链接:uva 11255 - Necklace
题目大意:给定3种颜色的珠子个数,要求所有的珠子都用上的情况下有多少种不同的项链,旋转翻转视为同一种。
解题思路:等价类的计数,polya。
- 旋转:有0,1,~ n-1步。
- 翻转:考虑n为奇数偶数,奇数下,有n条对称轴(过一点)偶数时,有n/2条过两点,n/2条不过点。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 40;
int N, col[3], u[3];
ll c[maxn+5][maxn+5];
void init () {
for (int i = 0; i <= maxn; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
int gcd (int a, int b) {
return b == 0 ? a : gcd (b, a % b);
}
ll solve (int k) {
int n = 0;
ll ret = 1;
for (int i = 0; i < 3; i++) {
if (u[i] % k)
return 0;
u[i] /= k;
n += u[i];
}
for (int i = 0; i < 3; i++) {
ret *= c[n][u[i]];
n -= u[i];
}
return ret;
}
ll polya () {
ll ret = 0;
for (int i = 0; i < N; i++) {
memcpy(u, col, sizeof(col));
ret += solve(N/gcd(i, N));
}
if (N&1) {
for (int i = 0; i < 3; i++) {
if (col[i]) {
memcpy(u, col, sizeof(col));
u[i]--;
ret += N * solve(2);
}
}
} else {
memcpy(u, col, sizeof(col));
ret += N/2 * solve(2);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (col[i] && col[j]) {
memcpy(u, col, sizeof(col));
u[i]--; u[j]--;
ret += N/2 * solve(2);
}
}
}
}
return ret / 2 / N;
}
int main () {
init();
int cas;
scanf("%d", &cas);
while (cas--) {
N = 0;
for (int i = 0; i < 3; i++) {
scanf("%d", &col[i]);
N += col[i];
}
printf("%lld\n", polya());
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。