Rascal Triangle
Time limit1sMemory limit128 MB
Given a recursively defined 'Rascal triangle' with a division-based rule, compute R(n,m) efficiently for n,m up to 50,000 across up to 1000 queries.
- Level
Medium6 of 10
- Topics
- Math, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
The Rascal triangle is built by rules similar to Pascal's triangle.
The top row is row 0. Row i contains i+1 numbers, numbered from 0 to i from left to right. R(i, j) denotes the j-th number in row i.
Positions outside the triangle are treated as 0.
R(n, m) = 0 (n < 0, m < 0, or m > n)
The first and last numbers of every row are 1.
R(n, 0) = R(n, n) = 1
Every other number is obtained by multiplying the west and east values, adding 1, and dividing by the north value.
Written as a formula:
R(n+1, m+1) = (R(n, m) * R(n, m+1) + 1) / R(n-1, m)
Given n and m, write a program that computes R(n, m).
Input
The first line contains the number of test cases T. (1 <= T <= 1,000)
Each test case is given on one line and consists of two integers n and m. (0 <= m <= n <= 50,000)
Output
For each test case, output R(n, m) on its own line.