Hackerrank - nCr table

Jim is doing his discrete maths homework which requires him to repeatedly calculate nCr(n choose r) for different values of n. Knowing that this is time consuming, he goes to his sister June for help. June, being a computer science student knows how to convert this into a computer program and generate the answers quickly. She tells him, by storing the lower values of nCr(n choose r), one can calculate the higher values using a very simple formula.

If you are June, how will you calculate nCr values for different values of n?

Since values will be large you have to calculate them modulo .

Input Format 
The first line contains the number of test cases T. 
T lines follow each containing an integer n.

Output Format 
For each n output the list of nC0 to nCn each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 109

Constraints 
1<=T<=200 
1<=n< 1000

Sample Input

3
2
4
5

Sample Output

1 2 1
1 4 6 4 1
1 5 10 10 5 1

Explanation 
For 2 we can check 2C0 2C1 and 2C2 are 1, 2 and 1 respectively. The other inputs' answer follow similar pattern.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const LL MOD = 1e9;
7. const double pi = 2 * acos (0.0);
8.  
9. int _Int(){int x; scanf("%d", &x); return x;}
10. LL _LLi(){LL x; scanf("%lld", &x); return x;}
11. void pruts(){puts("-1");exit(EXIT_SUCCESS);}
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. LL tab[ 1000+2 ][ 1000+2 ];
31.  
32. void table(){
33.     for( int i = 0; i <= 1001; i++ )tab[ i ][ 0 ] = 1LL;
34.     for( int i = 1; i <= 1001; i++ ){
35.         for( int j = 1; j <= 1001; j++ ){
36.             tab[ i ][ j ] = tab[ i-1 ] [ j ] + tab[ i-1 ] [ j-1 ];
37.             tab[ i ][ j ] %= MOD;
38.         }
39.     }
40. }
41.  
42. void Love(){
43.     table();
44.     int t = _Int();
45.     while( t-- ){
46.         int n = _Int();
47.         printf( "1");
48.         for( int i = 1; i <= n; i++ )printf(" %lld", tab[ n ][ i ] );
49.         puts("");
50.     }
51. }
52.  
53. int main(){
54.     #ifndef ONLINE_JUDGE
55. //        freopen("in.txt", "r", stdin);
56. //        freopen("n.txt", "w", stdout);
57.     #endif
58.     Love();
59.     return 0;
60. }