Given integers
Then we can calculate the sum of
var a = new Fraction64[p + 2];
var binom = new long[p + 2, p + 2];
for (var i = 0; i < p + 2; ++i)
{
binom[i, 0] = binom[i, i] = 1;
for (var j = 1; j < i; ++j)
binom[i, j] = binom[i - 1, j] + binom[i - 1, j - 1];
}
a[p + 1] = (1, p + 1); // (numerator, denominator)
for (var i = p; i > 0; --i)
{
a[i] = (0, 1);
var sign = 1;
for (var m = i + 1; m <= p + 1; ++m)
{
a[i] += sign * binom[m, i - 1] * a[m]; // overloaded operators * and + with division by GCD
sign *= -1;
}
a[i] /= i;
}
//Answer: a[1..p+1]
Complexity: Time –
Пусть у нас есть последовательность рациональных чисел
Тогда
В силу
Раскроем множитель
Представим
- В первой сумме
$k^u$ встречается один раз, при$i=u$ . Значит$b_u = a_u + \ldots$ . - Оставшиеся слагаемые берутся из раскрытия второй суммы - коэффициенты перед
$k^{i-j}$ . Чтобы их определить, нужно найти все такие$i$ и$j$ , что$i - j = u$ . Т.к.$0 \leq j \leq i \leq p + 1$ , то выражая$j$ через$i$ , получаем все решения:$i = m$ ,$j = m - u$ для$m$ из$[u..p+1]$
Таким образом
Т.к. выражение коэффициента
-
$a_{p+1}$ :
-
$a_{i} : 1 \leq i \leq p$ :
Таким образом, мы можем последовательно вычислять
Оценим вычислительную сложность.
-
Память –
$O(p^2)$ :
Нужно хранить$a_0, \ldots, a_{p+1}$ – это требует$O(p)$ памяти. Также нам нужно хранить биномиальные коэффициенты, чтобы не вычислять их каждый раз заново –$O(p^2)$ . -
Время –
$O(p^2)$ :
При вычислении каждого$a_i$ для$i \in [1..p]$ происходит суммирование$p - i + 1$ чисел – суммарно$O(1 + 2 + \ldots + p) = O(p^2)$ , а$a_{p+1}$ вычисляется за$O(1)$ . Предварительное вычисление биномиальных коэффициентов требует$O(p^2)$ времени.
Т.к. в компьютере дробные числа теряют точность,
Таким образом, нужно лишь просуммировать все
Считая, что
Временная сложность данного преобразования –