[Uva10601]Cubes
标签： 置换 burnside引理
题意
给你12跟长度相同的小木棍，每个小木棍有一个颜色。统计他们能拼成多少种不同的立方体。旋转后相同的立方体认为是相同的。
题解
这道题难就难在他不告诉你正方体是怎么旋转的，所以只要把这个想清楚了这道题就不是很难。
有三种旋转方式：
以一个面与其对面的中心为轴旋转。这个可以旋转90,180,270度。
以一条棱与其对棱的中心为轴旋转。只能旋转180度。
以一个点与其对点的中心为轴旋转。能旋转120和240度。（其实就是以这个点为端点的边在旋转）
然后就可以弄一个6维背包来求了（虽然组合数也可以，但是6维背包难道不更爽一些吗？）
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<vector>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
int cnt[7];
int dp[13][13][13][13][13][13];
ll ans=0;
void init()
{
memset(cnt,0,sizeof(cnt));
REP(i,1,12)cnt[read()]++;
ans=0;
}
int w[100],Cnt;
void Dp()
{
REP(a,0,cnt[1])REP(b,0,cnt[2])REP(c,0,cnt[3])REP(d,0,cnt[4])REP(e,0,cnt[5])REP(f,0,cnt[6])dp[a][b][c][d][e][f]=0;
dp[0][0][0][0][0][0]=1;
REP(l,1,Cnt)
{
DREP(a,cnt[1],0)
{
DREP(b,cnt[2],0)
{
DREP(c,cnt[3],0)
{
DREP(d,cnt[4],0)
{
DREP(e,cnt[5],0)
{
DREP(f,cnt[6],0)
{
if(a>=w[l])dp[a][b][c][d][e][f]+=dp[a-w[l]][b][c][d][e][f];
if(b>=w[l])dp[a][b][c][d][e][f]+=dp[a][b-w[l]][c][d][e][f];
if(c>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c-w[l]][d][e][f];
if(d>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d-w[l]][e][f];
if(e>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d][e-w[l]][f];
if(f>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d][e][f-w[l]];
}
}
}
}
}
}
}
}
void doing()
{
Cnt=12;
REP(i,1,12)w[i]=1;
Dp();
ans+=dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]];
Cnt=3;
REP(i,1,3)w[i]=4;
Dp();
ans+=6*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]];
Cnt=6;
REP(i,1,6)w[i]=2;
Dp();
ans+=3*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]];
Cnt=4;
REP(i,1,4)w[i]=3;
Dp();
ans+=8*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]];
Cnt=7;
w[1]=1;w[2]=1;
REP(i,3,7)w[i]=2;
Dp();
ans+=6*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]];
cout<<ans/24<<endl;
}
int main()
{
int t=read();
while(t)
{
t--;
init();
doing();
}
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
