시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 15 | 8 | 8 | 66.667% |
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번이다.
폴하버의 삼각형은 아래와 같이 구할 수 있다.
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