11651 - Krypton Number System

[tryit1]

any hints ?

[Chimed]

any hints ?

Make a graph.
Lets say base of krypton number is 3. (digits 0,1,2)
Initially we have a board is like this.
. 0 1 2
0 x 1 4
1 1 x 1
2 4 1 x
Now suppose we going 0 to 2 we need make score 4. Which means 3 dummy digits is necessary. Lets say them A(score 1), B(score 2), C(score 3).
Then we get this kind of graph
1
^
|
0->A->B->C->2
Same thing will be done 2 to 0. Lets call new dummy digit D(1 score), E(2 score), F(3 score)
New graph is
?0 1 2 A B C D E F
0 0 1 0 1 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0
2 0 1 0 0 0 0 1 0 0
A 0 0 0 0 1 0 0 0 0
B 0 0 0 0 0 1 0 0 0
C 0 0 1 0 0 0 0 0 0
D 0 0 0 0 0 0 0 1 0
E 0 0 0 0 0 0 0 0 1
F 1 0 0 0 0 0 0 0 0
Now we have a matrix. Lets say this matrix M. To get score of p we need to calculate exponential of matrix M.
M^(p-1)
This can be done N^3log(p) where N is size of M.
Now calculate M[1][0]+M[1][1]+M[1][2]+M[2][0]+M[2][1]+M[2][2].
Thats it, at least I hope so ...

[tryit1]

thanks , nice trick.

[raincole]

I get AC also with your hint.
Thanks.

[crip121]

im using matrix expo but it seems to be slow on input sets

Code: Select all

algo:
expo( p )
{
 if( p==1 ) 
   return base
 else
 {
  a = expo(p/2);
  b = a*a;
  if(p%2==1)
   a = a*base
  return a;
 }

so, for odd values of "p" im doing 2 matrix multiplication. so my algorithms complexity is actually 2*3^n*log(p). any idea how to reduce that ? ( base is the matrix when p = 1 )

[crip121]

hmm.. i reduced my matrix multiplication part from 2*n^3 to n^3.. and now getting WA
im doing all calculation on unsigned long without any mod operation and its giving me right answer in my compiler.. is it wrong ? should i use mod operation ?