10843 - Anne's game

[27584NX]

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]

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]

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]

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.

[yiuyuho]

Hi Abednego, can you share the dynamic programming method? Thanks

[yiuyuho]

I looked it up on amazon, I don't think I can find "The Book", who's the author?

[mf]

Look for 'Proofs from the Book'.

[yiuyuho]

Got it, Thanks!

[newton]

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;
}

advanced thanks

[mf]

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]

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;
}



please help

[Articuno]

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.

[mf]

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]

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 ]

[abid_iut]

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.
please help if there is any mistake and tell me where i am wrong.
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;
}