首页 > ACM题库 > HDU-杭电 > hdu 4237 The Rascal Triangle待解决[解题报告]C++
2015
05-23

hdu 4237 The Rascal Triangle待解决[解题报告]C++

The Rascal Triangle

问题描述 :

The Rascal Triangle definition is similar to that of the Pascal Triangle. The rows are numbered from the top starting with 0. Each row n contains n+1 numbers indexed from 0 to n. Using R(n,m) to indicte the index m item in the index n row:
  
R(n,m) = 0 for n < 0 OR m < 0 OR m > n

The first and last numbers in each row(which are the same in the top row) are 1:
  
R(n,0) = R(n,n) = 1

The interior values are determined by (UpLeftEntry*UpRightEntry+1)/UpEntry(see the parallelogram in the array below):
  
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)

Repeating Characters

Write a program which computes R(n,m) theRepeating Characterselement of theRepeating Charactersrow of the Rascal Triangle.

输入:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of 3 space separated decimal integers. The first integer is data set number, N. The second integer is row number n, and the third integer is the index m within the row of the entry for which you are to find R(n,m) the Rascal Triangle entry (0 <= m <= n <= 50,000).

输出:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of 3 space separated decimal integers. The first integer is data set number, N. The second integer is row number n, and the third integer is the index m within the row of the entry for which you are to find R(n,m) the Rascal Triangle entry (0 <= m <= n <= 50,000).

样例输入:

5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398

样例输出:

1 1
2 5
3 411495886
4 24383845
5 264080263