Page **1** of **1**

### 11609 - Teams

Posted: **Thu Jul 30, 2009 1:17 pm**

by **sharath**

The problem says that output has to be printed result modulo 1000000007, I dont understand why this value and moreover for n=3, the number of ways the coach can choose his team is:

First for k = 1, He has 3 ways,

for k = 2, He has 6 * 2 (For different captains) ways,

for k = 3, He has 1 * 3 (For different captains) ways,

So totally he has 3+12+3 = 18 ways, then 18 modulo 1000000007 is 18 itself. I don't understand how the output is given as 1.

Let me know if I have understood the problem correctly.

### Re: 11609 - Teams

Posted: **Fri Jul 31, 2009 9:18 pm**

by **emotional blind**

The first line of the input represents the number of cases in the input.

### 11609 ' Why WA !!

Posted: **Tue Jul 06, 2010 10:04 pm**

by **Psh**

Code: Select all

```
#include<stdio.h>
#include<math.h>
#define mod 1000000007
int main()
{
int n,i;
unsigned long m,p;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%lu",&m);
p=pow(2,(m-1));
printf("Case #%d: %lu\n",i,(m*p)%mod);
}
return 0;
}
```

### Re: 11609 ' Why WA !!

Posted: **Wed Jul 07, 2010 12:12 pm**

by **sohel**

What's your output for the input -> 1000000000

**pow(2,(1000000000-1))** .. this statement won't work due to overflow.

### Re: 11609 ' Why WA !!

Posted: **Wed Jul 07, 2010 12:34 pm**

by **Psh**

Thanks!!

I've fixed it. Got that point.

### Re: 11609 ' Why WA !!

Posted: **Wed Jul 07, 2010 12:46 pm**

by **sazzadcsedu**

Can U imagine what is the value of pow(2,m-1) where m=1000000000. Value of pow(2,31) is 2147483648.So i think you

can understand what pow(2,999999999) will return. So you have to write your own power function

where the intermediate result is mod(%) by 1000000007. And you can't avoid TLE by iteratively

calculating power, like using a for loop till N.There is a nice divide and conquer algorithm for calculating (b^p)%m ,where

b is base,p is power and m is mod.Try this.

### Re: 11609 ' Why WA !!

Posted: **Wed Jul 07, 2010 12:48 pm**

by **Psh**

Yes, Bro..

I'm trying it now Bigmod method.

### Re: 11609 ' Why WA !!

Posted: **Wed Jul 07, 2010 1:13 pm**

by **Psh**

Now I've got Accepted.

Thanks for helping.

### Re: 11609 - Teams

Posted: **Wed Feb 09, 2011 5:23 pm**

by **nymo**

I think, the answer is: summation of k * nCk for k = 1 ... n [nCk = n Choose k]

Can someone tell me how to get a closed form?

### Re: 11609 - Teams

Posted: **Fri Oct 14, 2011 11:20 pm**

by **plamplam**

It's easy to derive this summation formula...after deriving this, why don't you write down all the values of this summation from n = 1 to n = 7 on paper? May be you will notice a pattern. If you do notice a pattern may be you will understand why and how such a pattern exists. Good luck.

### Re: 11609 - Teams

Posted: **Fri Nov 07, 2014 5:44 pm**

by **richatibrewal**

I am not getting the required output: I m using the summation of k*nCk

Code: Select all

```
#include<cstdio>
using namespace std;
#define mod 1000000007;
int main()
{
int n,i,j,c=0,num,k;
long long int sum,res;
scanf("%d",&n);
while(n--)
{
c++;
sum=0;
scanf("%d",&k);
for(i=1;i<=k;i++)
{
res=i;
num=k;
for(j=1;j<=i;j++)
{
res=res*num;
res=res/j;
num--;
res=res%mod;
}
sum=sum+res;
sum=sum%mod;
//printf("%d %lld %lld\n",i,sum,res);
}
printf("Case #%d: %lld\n",c,sum);
}
return 0;
}
```

### Re: 11609 - Teams

Posted: **Wed Nov 19, 2014 1:18 am**

by **brianfry713**

Your code is getting TLE. Try input: