시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 203 75 60 54.054%

문제

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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgUyhuLG0pXHVjNzc0IFx1YzlkZFx1YzIxOFx1Yzc3NFx1YmE3NCAwLCBcdWQ2NDBcdWMyMThcdWM3NzRcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmluYXJ5IFN0aXJsaW5nIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBTdGlybGluZyBudW1iZXIgb2YgdGhlIHNlY29uZCBraW5kIFMobiwgbSkgc3RhbmRzIGZvciB0aGUgbnVtYmVyIG9mIHdheXMgdG8gcGFydGl0aW9uIGEgc2V0IG9mIG4gdGhpbmdzIGludG8gbSBub25lbXB0eSBzdWJzZXRzLiBGb3IgZXhhbXBsZSwgdGhlcmUgYXJlIHNldmVuIHdheXMgdG8gc3BsaXQgYSBmb3VyLWVsZW1lbnQgc2V0IGludG8gdHdvIHBhcnRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnsxLCAyLCAzfSBVIHs0fSwgezEsIDIsIDR9IFUgezN9LCB7MSwgMywgNH0gVSB7Mn0sIHsyLCAzLCA0fSBVIHsxfTxcL2xpPlxyXG5cdDxsaT57MSwgMn0gVSB7MywgNH0sIHsxLCAzfSBVIHsyLCA0fSwgezEsIDR9IFUgezIsIDN9LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgcmVjdXJyZW5jZSB3aGljaCBhbGxvd3MgdG8gY29tcHV0ZSBTKG4sIG0pIGZvciBhbGwgbSBhbmQgbi48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5TKDAsIDApID0gMTsgUyhuLCAwKSA9IDAgZm9yIG4gJmd0OyAwOyBTKDAsIG0pID0gMCBmb3IgbSAmZ3Q7IDA7PFwvbGk+XHJcblx0PGxpPlMobiwgbSkgPSBtIFMobiAtIDEsIG0pICsgUyhuIC0gMSwgbSAtIDEpLCBmb3IgbiwgbSAmZ3Q7IDAuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIG11Y2ggJnF1b3Q7ZWFzaWVyJnF1b3Q7LiBHaXZlbiBpbnRlZ2VycyBuIGFuZCBtIHNhdGlzZnlpbmcgMSAmbHQ7PSBtICZsdDs9IG4sIGNvbXB1dGUgdGhlIHBhcml0eSBvZiBTKG4sIG0pLCBpLmUuIFMobiwgbSkgbW9kIDIuPFwvcD5cclxuXHJcbjxwPkV4YW1wbGU8XC9wPlxyXG5cclxuPHA+Uyg0LCAyKSBtb2QgMiA9IDEuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBmb3IgZWFjaCBkYXRhIHNldDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgbiBhbmQgbSw8XC9saT5cclxuXHQ8bGk+Y29tcHV0ZXMgUyhuLCBtKSBtb2QgMiw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBleGFjdGx5IG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIGQgZXF1YWwgdG8gdGhlIG51bWJlciBvZiBkYXRhIHNldHMsIDEgJmxlOyBkICZsZTsgMjAwLiBUaGUgZGF0YSBzZXRzIGZvbGxvdy48XC9wPlxyXG5cclxuPHA+TGluZSBpICsgMSBjb250YWlucyB0aGUgaS10aCBkYXRhIHNldCAtIGV4YWN0bHkgdHdvIGludGVnZXJzIG48c3ViPmk8XC9zdWI+IGFuZCBtPHN1Yj5pPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIDEgJmxlOyBtPHN1Yj5pPFwvc3ViPiAmbGU7IG48c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgZXhhY3RseSBkIGxpbmVzLCBvbmUgbGluZSBmb3IgZWFjaCBkYXRhIHNldC4gTGluZSBpLCAxICZsZTsgaSAmbGU7IGQsIHNob3VsZCBjb250YWluIDAgb3IgMSwgdGhlIHZhbHVlIG9mIFMobjxzdWI+aTxcL3N1Yj4sIG08c3ViPmk8XC9zdWI+KSBtb2QgMi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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