I already found a way to convert the graph to a matrix, and the ans is the determinant of this matrix. But it seems so hard to get it.

There is another way to solve this problem

I have AC now, but can you E-mail me your method please
ykt836@gmail.com, thanks

Hi Genesis, Can You give me hint how did you to mod the determinant. I am having problem with it.


Edited by author 19.08.2008 09:39

Of course, the usual way of solving such problems is DP by profile. But method of Genesis is much more easier to implement. Thank you for idea!

I used JAVA's BigInteger, I can mod the determinant just before I print it

One can use extended euclid to do all calculations modulo 10^9 straightforwardly

10^9 isn't a prime number! How will you find for example ( 1/10 ) mod 10^9 ?

i can't understand.

when i solve the determinant of the matrix, there are decimal fraction indeed. how can you avoid it?

can you tell me in detail?

multiply their LCM

yumen , can not pass test 5.

I used BigInteger and Kirgoff determinant theorem.
Dp or divide and concur approach seems unimplementing.
Interesting who used nondeterminant approach.

I know simple and fast way to calculate the determinant of matrix by the integer modulo...
But I don't understand, how convert graph to a matrix(((

test 1 -
0110
1001
1001
0110 -  det =0

I used article in wiki
with key words  Kirgoff theorem

2 Cat36:
Mail to nick@inbox.ru using goryinyich as nick and I'll explain to you what you want, and you'll explain to me what I want =)))

Sorry, 3 weeks offline((
if it's still interest you, icq 4n7;8h8h8;0/3'3'5 (only digits)