프로그램 명: stirling
제한시간: 1 초
Stirling 수 S(n,m) 은 n 개의 원소를 m 개의 부분집합(공집합 제외)으로 나눌 수 있는 방법의 수를 나타낸다.
예를 들어 , 원소 4 개를 가진 집합을 두개로 나눌 수 있는 방법의 수 S(4,2) 는 7 이다.
{1, 2, 3} U {4}, {1, 2, 4} U {3}, {1, 3, 4} U {2}, {2, 3, 4} U {1}
{1, 2} U {3, 4}, {1, 3} U {2, 4}, {1, 4} U {2, 3}.
이는 다음과 같은 점화식으로 구할 수 있다.
- S(0, 0) = 1 , S(n, 0) = 0 , S(0, m) = 0 , n,m > 0
- S(n, m) = m S(n - 1, m) + S(n - 1, m - 1), n, m > 0.
우리가 할 일은 이 보다 더 쉽다. n 과 m ( 1 <= m <= n ) 이 주어질 때 S(n,m) 을 2 로 나눈 나머지를 구하는 것이다.
예를 들어 ,
S(4, 2) mod 2 = 1.
입력
첫 번 째 수는 테스트 데이터 수 d 가 주어진다. 1 <= d <= 200
다음 d 줄에 두개의 수 n , m 이 주어진다. 1 <= mi <= ni <= 10^9.
출력
0 혹은 1 을 출력한다.
입출력 예
입력
1
4 2
출력
1
출처: Central Europe 2001
[질/답]
[제출 현황]
[푼 후(0)]