https://www.acmicpc.net/problem/11500
11500번: Polynomial
A polynomial \(f(k)\) of degree \(t\) with integral coefficients is given as \(f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t\), where the coefficients \(c_0, \dots, c_t\) are all integers. Here, we are interested in the sum \(S(n)\) of \(f(0)\), \(f(1)\), .
www.acmicpc.net
전처리를 하면 쉬운데, 전처리 없이는 다소 복잡한 문제가 될 수 있을 것 같습니다.
일단 문제를 풀기 위해 주어진 식을 그대로 씁니다.
$$S(n) = \sum_{k=0}^{n} f(k) = \sum_{k=0}^{n} \sum_{i=0}^{t} c_{i} k^{i}$$
그런데 위를 잘 관찰하면 다음을 얻습니다. (잘 안 보일 경우 시그마로 묶인 식을 전부 써보면 쉬워집니다.)
$$S(n) = \sum_{i=0}^{t} \left \{ c_{i} \sum_{k=0}^{n} k^{i} \right \}$$
이로부터 문제가 exploit하라고 제공한 식을 쓸 여지가 보입니다.
이에 관한 설명은 1492번: 합 에서 작성하였고, 결과만을 보여드리자면
$$A(n,k) = \sum_{i=0}^{n} i^{k}$$
일 때 $A(n,k)$에 관한 점화식이 다음과 같습니다.
$$A(n,k) = \frac{ (n+1)^{k} - 1 - \sum_{i=0}^{k-1} \binom{k+1}{i} A(n,i) }{ \binom{k+1}{k} }$$
이로부터 $S(n)$을 다음과 같이 표현할 수 있습니다.
$$S(n) = \sum_{i=0}^{t} c_{i} A(n,i) $$
따라서 문제는 $A(n,i)$을 $n$에 관한 $i+1$차의 다항식으로 나타내면 해결됩니다. 점화식은 이미 나와있으므로 식 정리를 잘 해보면 해결될 것입니다. (제가 이 방향으로 풀이를 완성하지 않아서 이 풀이는 여기서 마무리하려합니다.)
아마도 정해는 위와 같겠지만, Bernoulli's Number $B_{n}$을 도입하면 보다 편한 풀이가 가능합니다.
위키피디아에 따르면, Faulhaber's Formula는 다음과 같이 표현할 수 있습니다. (단, $B_{1}^{+} = \frac{1}{2}$의 convention을 사용했습니다.)
$$ \sum_{k=1}^{n} k^{p} = \frac{1}{p+1} \sum_{j=0}^{p} \binom{p+1}{j} B_{j} n^{p+1-j} $$
이 방법이 정해보다 복잡할 순 있겠지만, 로컬에서 각 $B_{j}$를 구했을 때 식이 더 간단해지는 것 같습니다.
이 링크 에 따르면, $B_{1}^{+} = \frac{1}{2}$을 채택했을 때
$$ B_{m}^{+} = 1 - \sum_{k=0}^{m-1} \binom{m}{k} \frac{B_{k}^{+}}{m-k+1} $$
이므로, 식을 그대로 잘 구현하면 로컬에서 $B_{j}$을 구할 수 있습니다.
다만, Bernoulli's Number은 잘 알려진 수열이므로 인터넷에서 값을 쉽게 찾을 수 있습니다.
그러면 Bernoulli's Number을 도입했을 때 $S(n)$의 $n^{i}$의 coefficient가 어떻게 나타날 지 전개해보겠습니다.
$$ S(n) = \sum_{i=0}^{t} \left \{ c_{i} \sum_{j=0}^{n} j^{i} \right \} $$
$$ = c_{0}\sum_{j=0}^{n} j^{0} + \sum_{i=1}^{t} \left \{ c_{i} \sum_{j=0}^{n} j^{i} \right \} $$
$$ = c_{0} + c_{0} \sum_{j=1}^{n} j^{0} + \sum_{i=1}^{t} \left \{ c_{i} \sum_{j=1}^{n} j^{i} \right \} $$
$$ = c_{0} + \sum_{i=0}^{t} \left \{ c_{i} \sum_{j=1}^{n} j^{i} \right \} $$
$$ = c_{0} + \sum_{i=0}^{t} \left \{ c_{i} \times \frac{1}{i+1} \sum_{j=0}^{i} \binom{i+1}{j} B_{j}^{+} n^{i+1-j} \right \} $$
$$ = c_{0} + \sum_{i=1}^{t+1} \left \{ n^{i} \sum_{j=0}^{t+1-i} \frac{ \binom{j+i}{j} c_{j+i-1} }{j+i} \times B_{j}^{+} \right \} $$
(편의상 $0^{0}=1$의 convention을 사용했습니다.)
이제 Bernoulli's Number와 Binomial Coefficient를 전처리하면 각 케이스 당 시간복잡도 $O(t^{2})$에 문제가 해결됩니다. $a_{0}=c_{0}$임은 자명합니다.
제 코드는 다음과 같습니다.
#include <stdio.h>
long long ABS (long long a);
long long GCD (long long a, long long b);
typedef struct {
long long numerator;
long long denominator;
} fraction;
fraction reduction (fraction A);
fraction addition (fraction A, fraction B);
fraction multiply (fraction A, fraction B);
int main(void) {
long long binomial[27][27] = {{}};
for (int i = 0; i <= 26; i++) {
binomial[i][0] = binomial[i][i] = 1;
for (int j = 1; j < i; j++) {
binomial[i][j] = binomial[i-1][j] + binomial[i-1][j-1];
}
}
fraction Bernoulli_plus[27] =
{
{1, 1}, // 0
{1, 2}, // B+(1) = 1/2 and B-(1) = -1/2
{1, 6}, // 2
{0, 1},
{-1, 30}, // 4
{0, 1},
{1, 42}, // 6
{0, 1},
{-1, 30}, // 8
{0, 1},
{5, 66}, // 10
{0, 1},
{-691, 2730}, // 12
{0, 1},
{7, 6}, // 14
{0, 1},
{-3617, 510}, // 16
{0, 1},
{43867, 798}, // 18
{0, 1},
{-174611, 330}, // 20
{0, 1},
{854513, 138}, // 22
{0, 1},
{-236364091, 2730}, // 24
{0, 1},
{8553103, 6} // 26
};
int T;
scanf("%d", &T);
while(T--) {
int t;
scanf("%d", &t);
int array[26];
for (int i = 0; i <= t; i++) {
scanf("%d", &array[i]);
}
fraction result[27] = {{}};
for (int i = 1; i <= t + 1; i++) {
result[i] = reduction((fraction){binomial[i][0] * array[i-1], i});
for (int j = 1; j + i <= t + 1; j++) {
result[i] = addition(result[i],
multiply((fraction){binomial[j+i][j] * array[j+i-1], j+i}, Bernoulli_plus[j]));
}
}
long long answer = ABS(array[0]);
for (int i = 1; i <= t + 1; i++) {
answer += ABS(result[i].numerator);
}
printf("%lld\n", answer);
}
return 0;
}
long long ABS (long long a) {
return a > 0 ? a : -a;
}
long long GCD (long long a, long long b) {
while(b) {
long long temp = a % b;
a = b;
b = temp;
}
return a;
}
fraction reduction (fraction A) {
long long gcd = GCD(ABS(A.numerator), A.denominator);
A.numerator /= gcd;
A.denominator /= gcd;
return A;
}
fraction addition (fraction A, fraction B) {
return reduction((fraction)
{
A.numerator * B.denominator + B.numerator * A.denominator,
A.denominator * B.denominator
}
);
}
fraction multiply (fraction A, fraction B) {
return reduction((fraction)
{
A.numerator * B.numerator,
A.denominator * B.denominator
}
);
}(C11, 0ms, 1116KB, 제출번호 55701150)
Bernoulli's Number을 쓸 때의 장점이 있다면, 자료형의 크기가 어느정도까지 커져야할지 예측할 수 있다는 것입니다.
$t \leq 25$가 주어졌으므로 binomial coefficient의 최댓값은 $\binom{26}{13}=10400600$이며, $B_{n}^{+}$의 분모/분자 중 그 크기가 가장 큰 것은 $B_{24}^{+}$의 분자로, -236364091입니다. 따라서 주어진 범위에서 모든 $a_{i}$와 $b_{i}$ 값을 64비트 정수로 표현할 수 있습니다.
$$ |a_{i}| < (t+1) \times \binom{t+1}{\frac{t+1}{2}} \times c_{i} \times | \textrm{numerator}[B_{n}^{+}] | \leq 26 \times \binom{26}{13} \times 10 \times 236364091 < < 2^{63}-1$$
분모의 경우, $B_{n}$의 성질 중 $B_{2k+1}=0$을 활용하면, $b_{i} < 27!! \times 2730 < 2^{63}-1$ 입니다. (단, !! 기호는 double factorial 입니다.)