## 10843 - Anne's game

Moderator: Board moderators

27584NX
New poster
Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil
Contact:

### 10843 - Anne's game

Is this problem really about counting Connected Labelled Graphs with n vertices and n-1 edges?
I had came up with a permutation which (after factoring the numerator and denominator) ended up being wrong.
Is there any clue for this problem?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
There's a simple formula: n^(n-2).
It gives the number of distinct spanning trees in a complete graph on n vertices, and is called Cayley's formula.

27584NX
New poster
Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil
Contact:
Well, thank you very much.
Now I think the problem is reduced to simply going over a loop and getting results % 2000000011.
I'm going to look up why this formula works!
Thanks again,
Daniel

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
There is a book called "The Book", which has 7 beautiful proofs that this formula works. In this problem, the numbers are small enough that a fairly complicated dynamic programming solution works, too.
If only I had as much free time as I did in college...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Hi Abednego, can you share the dynamic programming method? Thanks yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
I looked it up on amazon, I don't think I can find "The Book", who's the author?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Look for 'Proofs from the Book'.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Got it, Thanks!

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10843 - Anne's game

why WA.
please give me some critical input output.
my code

Code: Select all

``````#include <cstdio>

int getMod(int a,int b,int c){
int i,n = a;
if(a == 1 || a == 2)
return 1;

for(i = 1; i< b; i++){
a *= n;
a %= c;
}
return a%c;
}

int main(){
int b,i,test;
//freopen("in.txt","rt",stdin);
scanf("%d",&test);
for(i = 1;i <= test; i++){
scanf("%d",&b);
printf("Case #%d: %d\n",i,getMod(b,b-2,2000000011));
}
return 0;
}``````
http://www.newton.0fees.net is enough! mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10843 - Anne's game

newton wrote:why WA.
Integer overflow.
please give me some critical input output.
This problem has only 100 inputs which can be easily generated - "(echo 100; seq 1 100) | ./your_program". Have you even tried running your program on them and simply looking at the results? Negative numbers in the output would have surely ringed a bell.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 10843 - Anne's game what is the problem??

where is the problem for this code
and what should i do to solve the problem
here is the code:

Code: Select all

``````#include<stdio.h>
#include<math.h>

int main()
{
long n,num,i,m,p;
scanf("%ld",&num);
for(int it=0;it<num;it++){
scanf("%ld",&n);
p=n;
if(n==1 || n==2){printf("1\n");continue;}
m=n-2;
for(i=1;i<m;i++){
p=p*n;
p=p%2000000011;
}
printf("%ld\n",p);
}
return 0;
}

``````
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10843 - Anne's game

Hi Abid,the problem in your code is you are using too straightforward approach. In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible if you just loop from 1 to 98 and store the result of multiplication in a variable. It will be a overflow.You have to use dynamic programming. I will give you some hint: Power(X,N) can be represented by the following formula:

power(X,N) =

{ 1, if N=0;
{ X*power(X,N-1), if N is odd;
{ power(X,N/2)^2, if N is even;

I have use this formula to solve the problem. It is a recursive as you can see. But it will also overflow if you do not combine it with the following idea:
That the ans will be ans%2000000011.
So.....the trick is:

"(X*Y)%M can be written as ((X%M)*(Y%M))%M ". So in the above formula you have to use this idea too if u want to get AC.
Otherwise the program will not work i think.
I hope it helps.
Good luck.
Last edited by Articuno on Mon Dec 01, 2008 5:27 pm, edited 2 times in total.
May be tomorrow is a better day............ mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10843 - Anne's game

Articuno wrote:In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible with traditional looping.
What's so impossible in a few hundreds of multiplications and divisions?
Modern CPUs do billions of those operations in mere seconds.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10843 - Anne's game

Well mf, thank u for your comments. In my reply to abid_iut, what i meant was :
if you do this type of thing:

Code: Select all

``````ans=1;
for(i=1;i<=98;i++)
{
ans=ans*100;
}``````
If i am right it will cause an overflow. In abid_iut's code, he does the similar thing and thus he is not getting the correct answer as there is an overflow. Yes, i may be wrong as i'm new in programming but in this case,i think u misunderstood me for my poor english.

I was not talking about machine's capability. I was talking about program's capability. You can not just use a loop to multiply 100 for 98 tmies and store it in a variable...it will certainly be a overflow.That's what i meant. Hope u understand and forgive me for my poor english.
Goodluck.
[I will also edit that part of my reply ]
May be tomorrow is a better day............ abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 10843 - Anne's game

hi Articuno
thankx for ur help but still it's not giving the correct ans.
for small numbers it is OK but for big numbers....... is this the way u told me to do or i missed something.
here is the code:

Code: Select all

``````#include<stdio.h>
#include<math.h>

int main()
{
long N,X,i,m,p,num,ans;
scanf("%ld",&num);
for(int it=0;it<num;it++){
scanf("%ld",&X);
N=X-2;
if(X==1 || X==2){printf("1\n");continue;}
for(i=1;i<=N;i++){
if(i%2==0){
ans=pow(X,(N/2))*pow(X,(N/2));
ans=ans%2000000011;
}
else if(i%2!=0){
ans=X*pow(X,N-1);
ans=ans%2000000011;
}
}
printf("%ld\n",ans);
}
return 0;
}

``````
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/