시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 86 41 31 58.491%

문제

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
4 2

예제 출력

1

힌트

출처

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

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