|
题目链接:uva 11255 - Necklace
题目大意：给定3种颜色的珠子个数，要求所有的珠子都用上的情况下有多少种不同的项链，旋转翻转视为同一种。
解题思路：等价类的计数，polya。
- 旋转：有0，1，~ n-1步。
- 翻转：考虑n为奇数偶数，奇数下，有n条对称轴（过一点）偶数时，有n/2条过两点，n/2条不过点。
#include
#include
#include
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; }
|