// http://uva.onlinejudge.org/external/120/12034.html
// Runtime: 0.016s
// Tag: Dp
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL res [1000 + 5];
void preCalc ()
{
res [0] = 1;
res [1] = 1; // when n = 1, res = 1
res [2] = 3; // when n = 2, res = 3
res [3] = 13;
LL numOfZeros [1000 + 5];
// numOfZeros [5] = number of binary numbers contain 5 zeros in a particular bit
for ( int i = 0; i < 1005; i++ ) numOfZeros [i] = 1;
numOfZeros [0] = 1;
numOfZeros [1] = 4;
numOfZeros [2] = 6;
numOfZeros [3] = 4;
for ( int i = 4; i <= 1000; i++ ) {
LL val = 0;
for ( int j = i - 1; j >= 0; j-- ) {
val += (numOfZeros [j] * res [j]) % 10056;
val %= 10056;
}
res [i] = val;
for ( int j = i; j >= 1; j-- ) {
numOfZeros [j] += numOfZeros [j - 1];
numOfZeros [j] %= 10056;
}
}
}
int main ()
{
preCalc();
int testCase; scanf ("%d", &testCase);
int cases = 0;
while ( testCase-- ) {
int n; scanf ("%d", &n);
printf ("Case %d: %lld\n", ++cases, res [n]);
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

can you “Briefly” explain what you have done on this code? i mean the process of the solution. i can’t understood what is the importance of the array you have used (numofZeros). thanks in advance.

ya i understand .. basically this idea is a bit complex .. let me try to make it clearer

first of all, take an example of four horses

how many ways, four horses can secure first place?

count the ways in binary

0000 -> invalid state

0001 -> 4th horse place first, others are 2nd/3rd/4th we dont care

0010 -> 3rd horse place first, others … we dont care

0011 -> both 3rd and 4th horse place first

0100 -> 2nd horse place first

…

…

…

1111 -> all horses place first

____________________________________

take the example, 0001 -> 4th horse place first

we don’t know the position of other horses

but we do know, 3 horses can end up race in 13 different ways

we can use this value to calculate the 4 horses case

for example,

if a horse place first in 3 horses case

then we can think of as, it place 2nd in 4 horses case .. because we already know which horse in first in 4 horses case

so, we know 3 information

1 horse can end up race in 1 ways

2 horses can end up race in 3 ways

3 horses can end up race in 13 ways

int ans_for_4_horses_case = 0;

we need to go through every possible case

0001 -> how many ways we can solve this case?

ans: in 13 ways …

first 3 horses end up race in 13 ways and 4th horse place first

ans_for_4_horses_case += 13;

0010 -> how many ways we can solve this case?

ans: 13 ways again

horse1, horse2 and horse4 end up race in 13 ways .. and horse3 place 1st

ans_for_4_horses_case += 13;

0011 -> ans_for_4_horses_case += 3;

0100 -> ans_for_4_horses_case += 13;

0101 -> ans_for_4_horses_case += 3;

0110 -> ans_for_4_horses_case += 3;

0111 -> ans_for_4_horses_case += 1;

1000 -> ans_for_4_horses_case += 13;

1001 -> ans_for_4_horses_case += 3;

1010 -> ans_for_4_horses_case += 3;

1011 -> ans_for_4_horses_case += 1;

1100 -> ans_for_4_horses_case += 3;

1101 -> ans_for_4_horses_case += 1;

1110 -> ans_for_4_horses_case += 1;

1111 -> ans_for_4_horses_case += 1;

print (ans_for_4_horses_case);

75

so, this is my basic idea .. now you can code it in your own way

if this thing still blur to you, you can post your comment again .. thanks 🙂

thanks brother. Its like easy as water to me now.