시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 147 57 44 54.321%

문제

n명을 m개의 그룹으로 나누는 방법의 수를 제 2종 스털링 수(Stirling numbers of the second kind)라고 하고, S(n,m)으로 표현한다. S(n,k)는 크기가 n인 집합을 k개의 공집합이 아닌 부분집합으로 나누는 방법의 수와 같다. 예를 들어, n=4, k=2일 때 다음과 같이 나눌 수 있다.

  • {1,2,3} ∪ {4}, {1,2,4} ∪ {3}, {1,3,4} ∪ {2}, {2,3,4} ∪ {1}
  • {1,2} ∪ {3,4}, {1,3} ∪ {2,4}, {1,4} ∪ {2,3}

S(n,m)은 다음과 같이 계산할 수 있다.

  • S(0,0) = 1
  • S(n,0) = 0 (n>0)
  • S(0,m) = 0 (m>0)
  • S(n,m) = mS(n-1,m) + S(n-1,m-1) (n,m > 0)

1 ≤ m ≤ n을 만족하는 n과 m이 주어졌을 때, S(n,m)가 짝수이면 0, 홀수이면 1을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 D가 주어진다. (1 ≤ D ≤ 200) 각 테스트 케이스는 한 줄로 이루어져 있고, n과 m이 공백으로 구분되져 있다. (1 ≤ m ≤ n ≤ 109)

출력

각 테스트 케이스에 대해서, S(n,m)이 짝수이면 0, 홀수이면 1을 출력한다.

예제 입력 1

1
4 2

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjM0NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVjMmE0XHVkMTM4XHViOWMxIFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+blx1YmE4NVx1Yzc0NCBtXHVhYzFjXHVjNzU4IFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM4MWMgMlx1Yzg4NSBcdWMyYTRcdWQxMzhcdWI5YzEgXHVjMjE4KFN0aXJsaW5nIG51bWJlcnMgb2YgdGhlIHNlY29uZCBraW5kKVx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIFMobixtKVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTQuIFMobixrKVx1YjI5NCBcdWQwNmNcdWFlMzBcdWFjMDAgblx1Yzc3OCBcdWM5ZDFcdWQ1NjlcdWM3NDQga1x1YWMxY1x1Yzc1OCBcdWFjZjVcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFjMTlcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIG49NCwgaz0yXHVjNzdjIFx1YjU0YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnsxLDIsM30gJmN1cDsgezR9LCB7MSwyLDR9ICZjdXA7IHszfSwgezEsMyw0fSAmY3VwOyB7Mn0sIHsyLDMsNH0gJmN1cDsgezF9PFwvbGk+XHJcblx0PGxpPnsxLDJ9ICZjdXA7IHszLDR9LCB7MSwzfSAmY3VwOyB7Miw0fSwgezEsNH0gJmN1cDsgezIsM308XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TKG4sbSlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5TKDAsMCkgPSAxPFwvbGk+XHJcblx0PGxpPlMobiwwKSA9IDAgKG4mZ3Q7MCk8XC9saT5cclxuXHQ8bGk+UygwLG0pID0gMCAobSZndDswKTxcL2xpPlxyXG5cdDxsaT5TKG4sbSkgPSBtUyhuLTEsbSkgKyBTKG4tMSxtLTEpIChuLG0gJmd0OyAwKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjEgJmxlOyBtICZsZTsgblx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFMobixtKVx1YWMwMCBcdWM5ZGRcdWMyMThcdWM3NzRcdWJhNzQgMCwgXHVkNjQwXHVjMjE4XHVjNzc0XHViYTc0IDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IERcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEQgJmxlOyAyMDApIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgblx1YWNmYyBtXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IG0gJmxlOyBuICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgUyhuLG0pXHVjNzc0IFx1YzlkZFx1YzIxOFx1Yzc3NFx1YmE3NCAwLCBcdWQ2NDBcdWMyMThcdWM3NzRcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzQ2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBTdGlybGluZyBOdW1iZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgU3RpcmxpbmcgbnVtYmVyIG9mIHRoZSBzZWNvbmQga2luZCBTKG4sIG0pIHN0YW5kcyBmb3IgdGhlIG51bWJlciBvZiB3YXlzIHRvIHBhcnRpdGlvbiBhIHNldCBvZiBuIHRoaW5ncyBpbnRvIG0gbm9uZW1wdHkgc3Vic2V0cy4gRm9yIGV4YW1wbGUsIHRoZXJlIGFyZSBzZXZlbiB3YXlzIHRvIHNwbGl0IGEgZm91ci1lbGVtZW50IHNldCBpbnRvIHR3byBwYXJ0czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT57MSwgMiwgM30gVSB7NH0sIHsxLCAyLCA0fSBVIHszfSwgezEsIDMsIDR9IFUgezJ9LCB7MiwgMywgNH0gVSB7MX08XC9saT5cclxuXHQ8bGk+ezEsIDJ9IFUgezMsIDR9LCB7MSwgM30gVSB7MiwgNH0sIHsxLCA0fSBVIHsyLCAzfS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZSBpcyBhIHJlY3VycmVuY2Ugd2hpY2ggYWxsb3dzIHRvIGNvbXB1dGUgUyhuLCBtKSBmb3IgYWxsIG0gYW5kIG4uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UygwLCAwKSA9IDE7IFMobiwgMCkgPSAwIGZvciBuICZndDsgMDsgUygwLCBtKSA9IDAgZm9yIG0gJmd0OyAwOzxcL2xpPlxyXG5cdDxsaT5TKG4sIG0pID0gbSBTKG4gLSAxLCBtKSArIFMobiAtIDEsIG0gLSAxKSwgZm9yIG4sIG0gJmd0OyAwLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyBtdWNoICZxdW90O2Vhc2llciZxdW90Oy4gR2l2ZW4gaW50ZWdlcnMgbiBhbmQgbSBzYXRpc2Z5aW5nIDEgJmx0Oz0gbSAmbHQ7PSBuLCBjb21wdXRlIHRoZSBwYXJpdHkgb2YgUyhuLCBtKSwgaS5lLiBTKG4sIG0pIG1vZCAyLjxcL3A+XHJcblxyXG48cD5FeGFtcGxlPFwvcD5cclxuXHJcbjxwPlMoNCwgMikgbW9kIDIgPSAxLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggZm9yIGVhY2ggZGF0YSBzZXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIG0sPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIFMobiwgbSkgbW9kIDIsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgZXhhY3RseSBvbmUgcG9zaXRpdmUgaW50ZWdlciBkIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzLCAxICZsZTsgZCAmbGU7IDIwMC4gVGhlIGRhdGEgc2V0cyBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPkxpbmUgaSArIDEgY29udGFpbnMgdGhlIGktdGggZGF0YSBzZXQgLSBleGFjdGx5IHR3byBpbnRlZ2VycyBuPHN1Yj5pPFwvc3ViPiBhbmQgbTxzdWI+aTxcL3N1Yj4gc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCAxICZsZTsgbTxzdWI+aTxcL3N1Yj4gJmxlOyBuPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGV4YWN0bHkgZCBsaW5lcywgb25lIGxpbmUgZm9yIGVhY2ggZGF0YSBzZXQuIExpbmUgaSwgMSAmbGU7IGkgJmxlOyBkLCBzaG91bGQgY29udGFpbiAwIG9yIDEsIHRoZSB2YWx1ZSBvZiBTKG48c3ViPmk8XC9zdWI+LCBtPHN1Yj5pPFwvc3ViPikgbW9kIDIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2001 B번

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