首页技术正文

UVa 10601 (Polya计数等价类计数) Cubes

工程师玉宸技术 2022年11月18日

0 收藏 788 点赞 3,500 浏览 1071 个字

用6种颜色去染正方体的12条棱，但是每种颜色都都限制了使用次数。

要确定正方体的每一条棱，可以先选择6个面之一作为顶面，然后剩下的四个面选一个作为前面，共有24种。

所以正方体的置换群共有24个置换。

具体每种置换的情况就是：UVA 10601 Cubes

幸运的是，任意一个置换中的循环节长度都是相同的(有一种置换除外)，所以在计算每个置换的“不动点”的时候就方便了很多。

调了好久调不对样例，后来发现C[0][0]没有初始化为1，=_=||

 #include <cstdio>
 #include <vector>
 #include <cstring>
 #include <cassert>
 using namespace std;
 typedef long long LL; int a[], b[];
 const int maxn = ;
 LL C[][]; LL cal(int k)//k为循环节长度
 {
     LL ans = ;
     vector<int> t;
     int num = ; //num为循环节的个数
     for(int i = ; i < ; i++)
     {
         if(a[i] % k == ) { t.push_back(a[i]/k); num += a[i]/k; }
         else return ;
     }
     for(int i = ; i < ; i++)
     {
         ans *= C[num][t[i]];
         num -= t[i];
     }
     return ans;
 } int main()
 {
     //freopen("in.txt", "r", stdin);     for(int i = ; i <= maxn; i++) C[i][] = C[i][i] = ;
     for(int i = ; i <= maxn; i++)
         for(int j = ; j <= i; j++)
             C[i][j] = C[i-][j] + C[i-][j-];     int T;
     scanf("%d", &T);
     while(T--)
     {
         memset(a, , sizeof(a));
         int x;
         for(int i = ; i < ; i++) { scanf("%d", &x); a[x-]++; }
         LL ans = ;
         ans += cal();  //原始排列
         ans +=  * cal();  //以两个对面的中心为轴旋转180°
         ans +=  *  * cal();  //以两个对面的中心为轴旋转90°或270°
         ans +=  *  * cal();  //以两个对角顶点为中心旋转
         for(int i = ; i < ; i++)
             for(int j = ; j < ; j++)
             {//以两个对棱中心连线为轴旋转180°
                 if(a[i] ==  || a[j] == ) continue;
                 a[i]--; a[j]--;//减去两个1循环
                 ans +=  * cal();
                 a[i]++; a[j]++;
             }
         printf("%lld\n", ans / );
     }     return ;
 }