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

  1. hdu 3547 DIY Cube (Ploya Theorem )

    DIY Cube Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total S ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 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 ...

  9. 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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. ( 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& ...

  5. 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 ...

  6. 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 -& ...

  7. 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...  

  8. 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 ...

  9. 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 ...

  10. 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 ...