网站建设学习什么,关于网站建设的请示范文,wifiu盘做网站,企业为什么做网站 图片Cubes
题意
给出121212根长度相等的木棒,颜色最多有666种,问能构成的本质不同的正方体数量.
题解
根据波利亚定理公式: 设X是元素集合,G是X的置换群,{u1,u2,...,uk}\{u_1,u_2,...,u_k\}{u1,u2,...,uk}是kkk种颜色的集合,CCC是XXX的任意着色集.这时,针对各颜色的数目的…Cubes
题意
给出121212根长度相等的木棒,颜色最多有666种,问能构成的本质不同的正方体数量.
题解
根据波利亚定理公式: 设X是元素集合,G是X的置换群,{u1,u2,...,uk}\{u_1,u_2,...,u_k\}{u1,u2,...,uk}是kkk种颜色的集合,CCC是XXX的任意着色集.这时,针对各颜色的数目的C的非等价着色数的生成函数是: PG(u1...uk,u12...uk2,...,u1n...ukn)P_G{(u_1...u_k,u_1^2...u_k^2,...,u_1^n...u_k^n)}PG(u1...uk,u12...uk2,...,u1n...ukn) 我们先求出121212根木棒的颜色数,假设有kkk中,每种颜色假设有{c1,c2,...,ck}\{c_1,c_2,...,c_k\}{c1,c2,...,ck}个,注意c1...ck12c_1...c_k12c1...ck12. 求出置换群. 众所周知的,正方体的置换群大小是242424. (1)恒等变换:111个 (2)绕对面的中心旋转90,180,27090,180,27090,180,270度:3∗393*3 93∗39个. (3)绕对边的中点连成的轴旋转180180180度:6∗166*1 66∗16个. (4)绕体对角线旋转120,240120,240120,240度:4∗284*284∗28个. 根据上述四种情况得到的关于线元素的置换平均值为: PG124(z1126z433z268z346z12z25)P_G\frac{1}{24}(z_1^{12}6z_4^33z_2^68z_3^46z_1^2z_2^5)PG241(z1126z433z268z346z12z25) 将zi∑u1iu2i...u6iz_i \sum{u_1^iu_2^i...u_6^i}zi∑u1iu2i...u6i代入PGP_GPG式.那么答案就是PGP_GPG函数的u1c1u2c2...ukcku_1^{c_1}u_2^{c_2}...u_k^{c_k}u1c1u2c2...ukck前的系数 PGP_GPG函数的每一项都是形如(u1...uk)a(u12...uk2)b...(u1n...ukn)z(u_1...u_k)^{a}(u_1^2...u_k^2)^{b}...(u_1^n...u_k^n)^{z}(u1...uk)a(u12...uk2)b...(u1n...ukn)z的,我要对每个这样的式子,求u1au2b...ukzu_1^au_2^b...u_k^zu1au2b...ukz前的系数之和.每个项单独进行dfsdfsdfs就可以了.
代码
#include iostream
#include algorithm
#include map
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)int T;
int tc[7],x[7],ox[7];
int C[13][13];void init() {C[0][0] 1;rep(i,1,12) {C[i][0] 1;rep(j,1,i) {C[i][j] C[i-1][j] C[i-1][j-1];}}
}
int ans 0;
void dfs(int dep,int mul) {if(dep 5) {int f 0;rep(i,1,6) f x[i];if(!f) {ans mul;}return ;}int tx[7];rep(i,1,6) tx[i] x[i];for(int x1 0;x1 tc[dep] dep * x1 tx[1];x1) {int res1 C[tc[dep]][x1];for(int x2 0;x2 tc[dep] - x1 dep*x2 tx[2];x2) {int res2 res1 * C[tc[dep]-x1][x2];for(int x3 0;x3 tc[dep]-x1-x2 dep*x3 tx[3];x3) {int res3 res2 * C[tc[dep]-x1-x2][x3];for(int x4 0;x4 tc[dep]-x1-x2-x3 dep*x4 tx[4];x4) {int res4 res3 * C[tc[dep]-x1-x2-x3][x4];for(int x5 0;x5 tc[dep]-x1-x2-x3-x4 dep*x5 tx[5];x5) {int res5 res4 * C[tc[dep]-x1-x2-x3-x4][x5];int x6 tc[dep]-x1-x2-x3-x4-x5;//pr(x1);pr(x2);pr(x3);pr(x4);pr(x5);pr(x6);if(dep*x6 tx[6]) {x[1] tx[1] - dep*x1;x[2] tx[2] - dep*x2;x[3] tx[3] - dep*x3;x[4] tx[4] - dep*x4;x[5] tx[5] - dep*x5;x[6] tx[6] - dep*x6;dfs(dep1,res5*mul);}}}}}}
}int main() {init();std::ios::sync_with_stdio(false);std::cin T;while(T--) {memset(ox,0,sizeof(ox));rep(i,1,12) {int tmp;std::cin tmp;ox[tmp] ;}int res 0;rep(i,1,6) x[i] ox[i];ans 0;tc[1] 12,tc[2] tc[3] tc[4] 0;dfs(1,1);res ans;rep(i,1,6) x[i] ox[i];ans 0;tc[1] tc[2] tc[3] 0,tc[4] 3;dfs(1,1);res 6*ans;rep(i,1,6) x[i] ox[i];ans 0;tc[1] tc[3] tc[4] 0,tc[2] 6;dfs(1,1);res 3*ans;rep(i,1,6) x[i] ox[i];ans 0;tc[1] tc[2] tc[4] 0,tc[3] 4;dfs(1,1);res 8*ans;rep(i,1,6) x[i] ox[i];ans 0;tc[1] 2,tc[2] 5,tc[3] tc[4] 0;dfs(1,1);res 6*ans;std::cout res/24 std::endl;}return 0;
}
