시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 5 5 55.556%

문제

1부터 n까지 m제곱의 합은 다음과 같다.

S(n,m) = SUM (j = i to n) (jm)

이 식은 n의 차수가 m+1인 다항식으로 나타낼 수 있다.

S(n,m) = SUM (k = 1 to m+1) (F(m,k) * nk)

예를 들면 다음과 같다.

S(n,1) = (1 + ... + n) = (1/2)*n2 + (1/2)*n
S(n,2) = (1 + ... + n2) = (1/3)*n3 + (1/2)*n2 + (1/6)*n
S(n,3) = (1 + ... + n3) = (1/4)*n4 + (1/2)*n3 + (1/4)*n2
S(n,4) = (1 + ... + n4) = (1/5)*n5 + (1/2)*n4 + (1/3)*n3 - (1/30)*n

위의 식에 나오는 계수 F(m,k)는 폴하버의 삼각형을 이룬다.

1            
1/2 1/2          
1/6 1/2 1/3        
0 1/4 1/2 1/4      
-1/30 0 1/3 1/2 1/5    
0 -1/12 0 5/12 1/2 1/6  
1/42 0 -1/6 0 1/2 1/2 1/7

F(m,k)에서 m은 행이고, 위에서부터 0번이다. k는 열이고, 왼쪽에서부터 1번이다.

폴하버의 삼각형은 아래와 같이 구할 수 있다.

  1. j>1인 F(i,j) = (i/j)*F(i-1,j-1)
  2. i번째 row의 수를 다 더했을 때 1이 되도록 F(i,1) 을 정해야 한다

m,k 가 주어졌을 때, F(m,k)를 구하는 프로그램을 작성하시오.

입력

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

출력

각 테스트 케이스에 대해서, F(m,k)를 출력한다. 만약 결과가 정수라면 정수로 출력하고, 정수가 아니라면, 기약분수로 출력한다.

예제 입력

4
4 1
4 3
86 79
400 401

예제 출력

-1/30
1/3
-22388337
1/401

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2012 Greater New York Programming Contest E번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: ntopia