시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 171 129 104 81.890%

문제

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

라스칼의 삼각형에서 가장 윗 줄은 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+XHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjhcdWM2NDAgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIyYlx1Yzc5MFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5SKG4sMCkgPSBSKG4sbikgPSAxPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1YmEzOFx1YzljMCBcdWFjMTJcdWM3NDQgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCAoXHVjMTFjXHVjYWJkXHVhYzEyICogXHViM2Q5XHVjYWJkXHVhYzEyICsgMSkgXC8gXHViZDgxXHVjYWJkXHVhYzEyIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wMSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDozMjdweDsgd2lkdGg6MzI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVhYzgzXHVjNzQ0IFx1YzIxOFx1YzJkZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NzRcdWJjZjRcdWJhNzQgUihuKzEsbSsxKSA9IChSKG4sbSkgKiBSKG4sbSsxKSArIDEpIFwvIFIobi0xLG0pIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzdjXHVjMmE0XHVjZTdjXHVjNzU4IFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YzExYyBSKG4sbSlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbHQ7PSBUICZsdDs9IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IDJcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIG5cdWFjZmMgbVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMCAmbHQ7PSBtICZsdDs9IG4gJmx0Oz0gNTAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBSKG4sbSlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Jhc2NhbF90cmlhbmdsZS5qcGdcIiBzdHlsZT1cImhlaWdodDoyNzlweDsgd2lkdGg6NTAwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI2NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgUmFzY2FsIFRyaWFuZ2xlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgUmFzY2FsIFRyaWFuZ2xlIGRlZmluaXRpb24gaXMgc2ltaWxhciB0byB0aGF0IG9mIHRoZSBQYXNjYWwgVHJpYW5nbGUuIFRoZSByb3dzIGFyZSBudW1iZXJlZCBmcm9tIHRoZSB0b3Agc3RhcnRpbmcgd2l0aCAwLiBFYWNoIHJvdyBuIGNvbnRhaW5zIG4gKyAxIG51bWJlcnMgaW5kZXhlZCBmcm9tIDAgdG8gbi4gVXNpbmcgUihuLCBtKSB0byBpbmRpY2F0ZSB0aGUgaW5kZXggbSBpdGVtIGluIHRoZSBpbmRleCBuIHJvdzo8XC9wPlxyXG5cclxuPHByZT5cclxuUihuLCBtKSA9IDAgZm9yIG4gJmx0OyAwIE9SIG0gJmx0OyAwIE9SIG0gJmd0OyBuPFwvcHJlPlxyXG5cclxuPHA+VGhlIGZpcnN0IGFuZCBsYXN0IG51bWJlcnMgaW4gZWFjaCByb3cgKHdoaWNoIGFyZSB0aGUgc2FtZSBpbiB0aGUgdG9wIHJvdykgYXJlIDE6PFwvcD5cclxuXHJcbjxwcmU+XHJcblIobiwgMCkgPSBSKG4sIG4pID0gMTxcL3ByZT5cclxuXHJcbjxwPlRoZSBpbnRlcmlvciB2YWx1ZXMgYXJlIGRldGVybWluZWQgYnkgKFVwTGVmdEVudHJ5KlVwUmlnaHRFbnRyeSArIDEpXC9VcEVudHJ5IChzZWUgdGhlIHBhcmFsbGVsb2dyYW0gaW4gdGhlIGFycmF5IGJlbG93KTo8XC9wPlxyXG5cclxuPHByZT5cclxuUihuICsgMSwgbSArIDEpID0gKFIobiwgbSkqUihuLCBtICsgMSkgKyAxKVwvUihuIC0gMSwgbSk8XC9wcmU+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Jhc2NhbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxODdweDsgd2lkdGg6MjMxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNvbXB1dGVzIFIobiwgbSkgdGhlIG0tdGggZWxlbWVudCBvZiB0aGUgbi10aCByb3cgb2YgdGhlIFJhc2NhbCBUcmlhbmdsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKCAxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBpcyBhIHNpbmdsZSBsaW5lIG9mIGlucHV0IGNvbnNpc3Rpbmcgb2YgMyBzcGFjZXMgc2VwYXJhdGVkIGRlY2ltYWwgaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyIGlzIGRhdGEgc2V0IG51bWJlciwgTi4gVGhlIHNlY29uZCBpbnRlZ2VyIGlzIHJvdyBudW1iZXIgbiwgYW5kIHRoZSB0aGlyZCBpbnRlZ2VyIGlzIHRoZSBpbmRleCBtIHdpdGhpbiB0aGUgcm93IG9mIHRoZSBlbnRyeSBmb3Igd2hpY2ggeW91IGFyZSB0byBmaW5kIFIobiwgbSkgdGhlIFJhc2NhbCBUcmlhbmdsZSBlbnRyeSAoIDAgJmxlOyBtICZsZTsgbiAmbGU7IDUwMDAwKTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIE4sIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIHdoaWNoIGlzIHRoZW4gZm9sbG93ZWQgYnkgdGhlIFJhc2NhbCBUcmlhbmdsZSBlbnRyeSBSKG4sIG0pIGFjY3VyYXRlIHRvIHRoZSBuZWFyZXN0IGludGVnZXIgdmFsdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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