Soluție HackerRank pentru nCr table, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: nCr table
- Domeniu: Combinatorics
- Limbaj: C++14
Challenge: nCr table
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464726583
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/ncr-table/problem
Cerință
Jim is doing his discrete maths homework which requires him to repeatedly calculate <sup>n</sup>C<sub>r</sub>(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 <sup>n</sup>C<sub>r</sub>(n choose r), one can calculate the higher values using a very simple formula.
If you are June, how will you calculate <sup>n</sup>C<sub>r</sub> values for different values of n?
Since ^nC_rvalues will be large you have to calculate them modulo 10^9.
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 <sup>n</sup>C<sub>0</sub> to <sup>n</sup>C<sub>n</sub> each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 10<sup>9</sup>
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 <sup>2</sup>C<sub>0</sub> <sup>2</sup>C<sub>1</sub> and <sup>2</sup>C<sub>2</sub> are 1, 2 and 1 respectively. The other inputs' answer follow similar pattern.
Cod sursă
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define P 1000000000
using namespace std;
int main()
{
long a[1000][1000];
for(int i=0;i<1000;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0)
a[i][j]=1;
else if(i==j)
a[i][j]=1;
else
a[i][j]=(a[i-1][j-1]%P + a[i-1][j]%P)%P;
}
}
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int j=0;j<=n;j++)
cout<<a[n][j]<<" ";
cout<<endl;
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}