Uva 10943 楊輝三角形wiki

1. // 10943 ------- how do you add
2. // https://zh.wikipedia.org/wiki/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2
3. // C_{{n}}^{{i}}=C_{{n-1}}^{{i-1}}+C_{{n-1}}^{{i}}
4. #include <iostream>
5. using namespace std;
6. int main()
7. {
8. int i,j;
9. int iInN,iInK;          // your input n and k
10. long long int lliChoices[201][201] = {0};         // index is over 100 because if iInK is 100 and iInN is 100  
11. for ( i=0 ; i<201 ; i++ )                         // sum will be about 199
12.     lliChoices[i][0] = 1;
14. for ( i=1 ; i<201 ; i++ )  
15.     for ( j=1 ; j<=i ; j++ )             // i and j can't be 0  
16.         lliChoices[i][j] = (lliChoices[i-1][j] + lliChoices[i-1][j-1]) % 1000000;
18. while ( cin >> iInN >> iInK )
19.     {
20.     if ( iInN == 0 && iInK == 0 )
21.         break;
22.     else
23.         cout << ( lliChoices[iInN+iInK-1][iInK-1]  ) << endl;          // 20 2    C{20+2-1}^{2-1}      
24.     }      
25.    
26. }

ex:     C[1][1] = C[0][1] + C[0][0]
result:     1      =   0         +        1
ex:     C[2][1] = C[1][1] + C[1][0]
result:     2      =    1        +        1

ex:     C[2][2] = C[1][2] + C[1][1]
result:     1      =   0         +        1

ex:     C[3][1] = C[2][1] + C[2][0]
result:     3      =   2         +        1

...