시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 179 137 112 82.963%

문제

라스칼의 삼각형은 파스칼의 삼각형과 비슷하다.

라스칼의 삼각형에서 가장 윗 줄은 0번 줄이다. i번째 줄에는 i+1개의 숫자가 들어있고, 차례대로 0번부터 i번이다. R(i,j)는 i번 줄의 j번째 숫자이다.

R(n,m) = 0 (n<0 or m<0 or m>n)

각 줄의 첫 번째와 마지막 숫자는 1이다.

R(n,0) = R(n,n) = 1

나머지 값을 채우는 방법은 (서쪽값 * 동쪽값 + 1) / 북쪽값 이다.

이것을 수식으로 표현해보면 R(n+1,m+1) = (R(n,m) * R(n,m+1) + 1) / R(n-1,m) 이다.

라스칼의 삼각형에서 R(n,m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 2개의 숫자 n과 m으로 이루어져 있다. (0 <= m <= n <= 50,000)

출력

각 테스트 케이스에 대해서 한 줄에 하나씩 R(n,m)을 출력한다.

예제 입력 1

5
4 0
4 2
45678 12345
12345 9876
34567 11398

예제 출력 1

1
5
411495886
24383845
264080263

힌트

W3sicHJvYmxlbV9pZCI6IjI2NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3N2NcdWMyYTRcdWNlN2MgXHVjMGJjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI3N2NcdWMyYTRcdWNlN2NcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1ZDMwY1x1YzJhNFx1Y2U3Y1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWFjZmMgXHViZTQ0XHVjMmI3XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI3N2NcdWMyYTRcdWNlN2NcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3MTcgXHVjOTA0XHVjNzQwIDBcdWJjODggXHVjOTA0XHVjNzc0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpKzFcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YWNlMCwgXHVjYzI4XHViODQwXHViMzAwXHViODVjIDBcdWJjODhcdWJkODBcdWQxMzAgaVx1YmM4OFx1Yzc3NFx1YjJlNC4gUihpLGopXHViMjk0IGlcdWJjODggXHVjOTA0XHVjNzU4IGpcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5SKG4sbSkgPSAwIChuJmx0OzAgb3IgbSZsdDswIG9yIG0mZ3Q7bik8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4XHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+UihuLDApID0gUihuLG4pID0gMTxcL3A+XHJcblxyXG48cD5cdWIwOThcdWJhMzhcdWM5YzAgXHVhYzEyXHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgKFx1YzExY1x1Y2FiZFx1YWMxMiAqIFx1YjNkOVx1Y2FiZFx1YWMxMiArIDEpIFwvIFx1YmQ4MVx1Y2FiZFx1YWMxMiBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcDEoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzI3cHg7IHdpZHRoOjMyN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YWM4M1x1Yzc0NCBcdWMyMThcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTc0XHViY2Y0XHViYTc0IFIobisxLG0rMSkgPSAoUihuLG0pICogUihuLG0rMSkgKyAxKSBcLyBSKG4tMSxtKSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yjc3Y1x1YzJhNFx1Y2U3Y1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWMxMWMgUihuLG0pXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmx0Oz0gVCAmbHQ7PSAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAyXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MCBuXHVhY2ZjIG1cdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDAgJmx0Oz0gbSAmbHQ7PSBuICZsdDs9IDUwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgUihuLG0pXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yYXNjYWxfdHJpYW5nbGUuanBnXCIgc3R5bGU9XCJoZWlnaHQ6Mjc5cHg7IHdpZHRoOjUwMHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFJhc2NhbCBUcmlhbmdsZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIFJhc2NhbCBUcmlhbmdsZSBkZWZpbml0aW9uIGlzIHNpbWlsYXIgdG8gdGhhdCBvZiB0aGUgUGFzY2FsIFRyaWFuZ2xlLiBUaGUgcm93cyBhcmUgbnVtYmVyZWQgZnJvbSB0aGUgdG9wIHN0YXJ0aW5nIHdpdGggMC4gRWFjaCByb3cgbiBjb250YWlucyBuICsgMSBudW1iZXJzIGluZGV4ZWQgZnJvbSAwIHRvIG4uIFVzaW5nIFIobiwgbSkgdG8gaW5kaWNhdGUgdGhlIGluZGV4IG0gaXRlbSBpbiB0aGUgaW5kZXggbiByb3c6PFwvcD5cclxuXHJcbjxwcmU+XHJcblIobiwgbSkgPSAwIGZvciBuICZsdDsgMCBPUiBtICZsdDsgMCBPUiBtICZndDsgbjxcL3ByZT5cclxuXHJcbjxwPlRoZSBmaXJzdCBhbmQgbGFzdCBudW1iZXJzIGluIGVhY2ggcm93ICh3aGljaCBhcmUgdGhlIHNhbWUgaW4gdGhlIHRvcCByb3cpIGFyZSAxOjxcL3A+XHJcblxyXG48cHJlPlxyXG5SKG4sIDApID0gUihuLCBuKSA9IDE8XC9wcmU+XHJcblxyXG48cD5UaGUgaW50ZXJpb3IgdmFsdWVzIGFyZSBkZXRlcm1pbmVkIGJ5IChVcExlZnRFbnRyeSpVcFJpZ2h0RW50cnkgKyAxKVwvVXBFbnRyeSAoc2VlIHRoZSBwYXJhbGxlbG9ncmFtIGluIHRoZSBhcnJheSBiZWxvdyk6PFwvcD5cclxuXHJcbjxwcmU+XHJcblIobiArIDEsIG0gKyAxKSA9IChSKG4sIG0pKlIobiwgbSArIDEpICsgMSlcL1IobiAtIDEsIG0pPFwvcHJlPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yYXNjYWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg3cHg7IHdpZHRoOjIzMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBjb21wdXRlcyBSKG4sIG0pIHRoZSBtLXRoIGVsZW1lbnQgb2YgdGhlIG4tdGggcm93IG9mIHRoZSBSYXNjYWwgVHJpYW5nbGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICggMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgaXMgYSBzaW5nbGUgbGluZSBvZiBpbnB1dCBjb25zaXN0aW5nIG9mIDMgc3BhY2VzIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBpcyBkYXRhIHNldCBudW1iZXIsIE4uIFRoZSBzZWNvbmQgaW50ZWdlciBpcyByb3cgbnVtYmVyIG4sIGFuZCB0aGUgdGhpcmQgaW50ZWdlciBpcyB0aGUgaW5kZXggbSB3aXRoaW4gdGhlIHJvdyBvZiB0aGUgZW50cnkgZm9yIHdoaWNoIHlvdSBhcmUgdG8gZmluZCBSKG4sIG0pIHRoZSBSYXNjYWwgVHJpYW5nbGUgZW50cnkgKCAwICZsZTsgbSAmbGU7IG4gJmxlOyA1MDAwMCk8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBOLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSB3aGljaCBpcyB0aGVuIGZvbGxvd2VkIGJ5IHRoZSBSYXNjYWwgVHJpYW5nbGUgZW50cnkgUihuLCBtKSBhY2N1cmF0ZSB0byB0aGUgbmVhcmVzdCBpbnRlZ2VyIHZhbHVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: newton08