Topic link ：http://acm.hdu.edu.cn/showproblem.php?pid=3547

The main idea of the topic ： Seek to use $C$ Two colors for the cube 8 The essence of vertex coloring is different . The essence of the two methods is different, that is, they can't make the two cubes have the same dyeing situation by rotating the cube .

A brief explanation of the problem ： First of all, we can get some results 24 It's a combined rotation . according to Polya Theorem and Lagrange theorem in group theory , Then think about it for yourself , You can get ：$Ans=\frac{x^8+Ax^4+Bx^2+Cx}{24}$, Do you know 3 An unknown number , And then the sample happens to have 3 Group data , So you can solve the equation and get $A=17,B=6,C=0$. Notice that the third data is modulus $10^{15}$ Subordinate , But obviously $112^4$ The fourth power of is not more than $10^{15}$, So it can also be used . In the end, high precision is enough .

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define K 10

#define D 15 const int T[] = {, , , , };

int Case, n; struct Big

{

int len, num[];

Big () {len = ; memset(num, , sizeof(num));}

void init(int k)

{

len = ;

memset(num, , sizeof(num));

for (; k; k /= K)

num[++ len] = k % K;

len = max(len, );

}

void Add(Big a)

{

len = max(len, a.len);

for (int i = ; i <= len; i ++)

num[i] += a.num[i];

for (int i = ; i < len; i ++)

if (num[i] >= K)

{

num[i + ] ++;

num[i] -= K;

}

if (num[len] >= K)

{

num[len + ] = ;

num[len ++] -= K;

}

}

void Times(Big a)

{

Big b;

b.len = len + a.len - ;

for (int i = ; i <= len; i ++)

for (int j = ; j <= a.len; j ++)

b.num[i + j - ] += num[i] * a.num[j];

for (int i = ; i < b.len; i ++)

if (b.num[i] >= K)

{

b.num[i + ] += b.num[i] / K;

b.num[i] %= K;

}

while (b.num[b.len] >= K)

{

b.num[b.len + ] += b.num[b.len] / K;

b.num[b.len ++] %= K;

}

len = b.len;

for (int i = ; i <= len; i ++)

num[i] = b.num[i];

}

void Multi(int k)

{

for (int i = ; i <= len; i ++)

num[i] *= k;

for (int i = ; i < len; i ++)

if (num[i] >= K)

{

num[i + ] += num[i] / K;

num[i] %= K;

}

while (num[len] >= K)

{

num[len + ] += num[len] / K;

num[len ++] %= K;

}

}

void Divide(int k)

{

for (int i = len; i >= ; i --)

{

if (i > ) num[i - ] += (num[i] % k) * K;

num[i] /= k;

}

for (; !num[len] && len > ; len --) ;

}

void out()

{

for (int i = min(D, len); i; i --)

printf("%d", num[i]);

puts("");

}

}A[], Ans; int main()

{

scanf("%d", &Case);

for (int Test = ; Test <= Case; Test ++)

{

scanf("%d", &n);

A[].init(n), Ans.init();

for (int i = ; i <= ; i ++)

{

A[i] = A[i - ];

A[i].Times(A[i - ]);

A[i].Multi(T[i]);

Ans.Add(A[i]);

A[i].Divide(T[i]);

}

Ans.Divide();

printf("Case %d: ", Test);

Ans.out();

}

return ;

}

HDOJ 3547

#include <cstdio>

typedef long long LL;

#define Mod 10000000000000000LL const int Base[] = {, , , };

const LL Ans[] = {0LL, 23LL, 296LL, 2675058176LL}; struct Frac

{

LL fz, fm;

Frac (LL _fz = 0LL, LL _fm = 0LL) {fz = _fz, fm = _fm;}

LL Abs(LL x)

{

return x > ? x : -x;

}

LL gcd(LL x, LL y)

{

return !y ? x : gcd(y, x % y);

}

void Simplify()

{

LL d = gcd(Abs(fz), Abs(fm));

fz /= d, fm /= d;

if (fm < ) fm = -fm, fz = -fz;

}

Frac operator + (const Frac a)

{

Frac b;

b.fz = fz * a.fm + fm * a.fz;

b.fm = fm * a.fm;

b.Simplify();

return b;

}

Frac operator - (const Frac a)

{

Frac b;

b.fz = fz * a.fm - fm * a.fz;

b.fm = fm * a.fm;

b.Simplify();

return b;

}

Frac operator * (const Frac a)

{

Frac b;

b.fz = fz * a.fz;

b.fm = fm * a.fm;

b.Simplify();

return b;

}

Frac operator / (const Frac a)

{

Frac b;

b.fz = fz * a.fm;

b.fm = fm * a.fz;

b.Simplify();

return b;

}

void out()

{

printf("%lld/%lld\n", fz, fm);

}

}X[][], Y[]; inline void Gauss()

{

for (int i = ; i < ; i ++)

for (int j = i + ; j <= ; j ++)

{

Frac t = X[j][i] / X[i][i];

for (int k = i; k <= ; k ++)

X[j][k] = X[j][k] - X[i][k] * t;

Y[j] = Y[j] - Y[i] * t;

}

for (int i = ; i; i --)

{

Frac sum;

sum.fz = 0LL, sum.fm = 1LL;

for (int j = i + ; j <= ; j ++)

sum = sum + X[i][j] * Y[j];

Y[i] = (Y[i] - sum) / X[i][i];

}

} int main()

{

for (int i = ; i <= ; i ++)

{

for (int j = ; j; j --)

{

if (j == ) X[i][j].fz = Base[i];

else X[i][j].fz = X[i][j + ].fz * X[i][j + ].fz;

X[i][j].fm = 1LL;

}

Y[i].fz = Ans[i], Y[i].fm = 1LL;

}

Gauss();

for (int i = ; i <= ; i ++)

Y[i].out();

return ;

}

HDOJ 3547 (Gauss)

## HDOJ 3547 DIY Cube More related articles on problem solving report

- hdu 3547 DIY Cube （Ploya Theorem ）
DIY Cube Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total S ...

- codeforces A. Black-and-White Cube Problem solving report
Topic link :http://codeforces.com/problemset/problem/323/A The title mean : Given value k , Need output k individual k That's ok k What color does the unit cube of a column represent ( Or black or ...

- ACM -- Algorithm summary （ 7、 ... and ）Phone list Problem solving report
HDOJ -- Phone list Problem solving report Problem description : Give me some phone numbers , If there is a common prefix, output NO, If not, output YES. The key to solving the problem is : Sort phone numbers by string , Compare neighboring phone numbers Sa ...

- CH Round #56 - National Day Happy competition problem solving report
lately CH There are a lot of games on the table , I will write all the problem-solving reports here , Let's talk about the methods and skills of solving problems . T1 Magic forest describe Cortana Came to a magic forest , This forest can be seen as a N*M Matrix , There is a tree at each position in the matrix ...

- The second mock exam 13day1 Problem solving report
The second mock exam 13day1 Problem solving report T1. transmitting station (station) N A launch station , Every launch station has a height hi, Transmit signal strength vi, The signal of each transmitting station will only be received by the first one higher than him on the left and right . Now look for the transmitter with the strongest signal . It took me time to recover ...

- BZOJ 1051 The most popular cattle Problem solving report
The topic is right here ! 1051: [HAOI2006] Popular cattle Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4438 Solved: 2353[S ...

- exercises ：codevs 2822 Love is in the heart Problem solving report
This report is about tarjan Algorithm is a problem with large amount of thinking ( It's really original , I hope the administrator will not move the article out of the home page ). I have done this problem before , But today due to review tarjan Algorithm , So you see codevs Classified strong link ...

- exercises ：codevs 1035 Train stop problem solving report
Ben konjac has come to write the problem solving report again . The title of this time is codevs 1035 The train stops . The main idea of the title is to give m The arrival time of a train . The length of stay and the value of the goods on board , What's at the station n A driveway , The train stops at the station once and gets the value of the goods on board 1% The profits of the ...

- exercises ： codevs 2492 Seven minutes of God's problem making 2 Problem solving report
This problem has been greatly influenced MagHSK I was inspired to come up with , Konjac thinks his code is similar to MagHSK Da Zhen's code is not as good as , So konjac is used here MagHSK Da Zhen's code ( You can follow my blog , Links are big MagHS ...

## Random recommendation

- BZOJ1017: [JSOI2008] Warcraft map DotR
Portal set up $f[i][j][k]$ For the second time $i$ A little bit , Contribute to the parent node $j$ A synthetic device , It cost $k$ The price of , The most power gained . pure $f[i][j][k]$ It's hard to transfer , The main reason is that it can't be maintained and other things ...

- Deep learning： forty-six (DropConnect Simple understanding )
and maxout(maxout Simple understanding ) equally ,DropConnect Also in ICML2013 Published on , It's also to improve Deep Network The generalization ability of , Both claim to be right Dropout(Dropout Simple ...

- Android Threads ---UI Thread and non thread UI Interthread communication
Recently, I learned thread by myself , It took a whole morning to make the master . Communication between threads . When the main thread sendMessage after , The child thread will call handleMessage To get what you sent Message. My main thread ...

- ( turn )JS Pass values between pages
One :JavaScript Static page value transfer URL piece Yes URL Carry out value transmission . Connect the message to URL On . Example : Parameters out of the page Post.htm—> <input type="text& ...

- php Time shift
Data read out in the database , It's all character type , So you need to switch : Time conversion : use date () Function to implement the time format ; date() The default time of the function is 1970/01/01/ 00:00:00; To get the time you want, you have to use ...

- ECSHOP User reviews
Can you do without auditing ? Now user reviews need to be reviewed before they can be displayed , I don't need to audit it to display it ? See this problem on the Forum , By the way, record it . This is OK , Here are the steps backstage -> System settings -> Store settings -& ...

- Years of wish , At last , Tears welled up in my eyes ...Adrew NG Of machine learning
thank you Andrew teacher ! thank you Coursera! Thank you for ! I hope it's a good start ! I hope I can use machine learning to make a better world...

- Baidu statistics API Use
Baidu statistics API Use When building your own blog , I hope I can have a log system , Be able to see PV.UV Etc , At the same time, I also built a ELK System , Unfortunately, the server configuration is too low (1GHZ+1G Memory ), It doesn't work at all . You can only use a third party's Day ...

- linux Basis and vim Basic use
Liunx Basics 1. Catalog /: root directory , Generally, the root directory only stores the directory , stay linux There is only one root directory under . Everything starts here , for example :/home It's just starting from the root directory / Start , Go back to home Catalog . /bin ...

- Manjaro Initial configuration ----anaconda-pycharm-opencv-tensorflow
1. Install Python 1) install yaourt anaconda source /opt/anaconda/bin/active root 2) Add environment variables stay 〜/ .bashrc Add export PATH ...