解題區/解題區 - UVa

UVa 766 - Sum of powers

contents

  1. 1. 題目描述
  2. 2. Solution

題目描述

$$\begin{align*} & \sum_{i = 1}^{n} i = \frac{n(n+1)}{2} \\ & \sum_{i = 1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} \\ & ... \\ & \sum_{i = 1}^{n} i^{k} = ? \\ \end{align*}$$

求 k < 20 的所有情況，並且把方程式列出。

Solution

當初在推倒$\sum_{i = 1}^{n} i^{2}$ 的時候，採用的方式如下：

首先，升一次觀察：

$$\begin{align*} & (i + 1)^{3} - i^{3} = 3i^{2} + 3i + 1 \end{align*}$$

整理，將$i^{2}$ 移到單獨項

$$\begin{align*} & i^{2} = \frac{1}{3} ((i + 1)^{3} - i^{3} - 3i - 1) \\ & \Rightarrow \sum_{i = 1}^{n} i^{2} = \sum_{i = 1}^{n} \frac{1}{3} ((i + 1)^{3} - i^{3} - 3i - 1) \end{align*}$$

此時特別計算$\sum_{i = 1}^{n} (i + 1)^{3} - i^{2}$，易見答案為$(n+1)^{3} - 1$

最後得到
$$\begin{align*} & \Rightarrow \sum_{i = 1}^{n} i^{2} = \frac{1}{3} ((n+1)^{3} - 1 + \sum_{i = 1}^{n} (-3i-1)) \end{align*}$$

藉由上述的推倒過程，可以擴充至更高維度的計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long C[25][25] = {};
long long M[25] = {}, A[25][25] = {};
long long llabs(long long v) {
    return v < 0 ? -v : v;
}
void init() {
    C[0][0] = 1;
    for(int i = 1; i < 25; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    // sum of powers
    M[0] = 1, A[0][1] = 1; // sigma(k^0) = n
    for(int i = 1; i <= 20; i++)  {
        M[i] = i + 1;
        long long val = 1;
        for(int j = 0; j <= i - 1; j++)
            val = val / __gcd(val, M[j]) * M[j];
        M[i] *= val;
//		printf("%lld %lld\n", M[i], val);
        for(int j = 0; j <= i - 1; j++)
            for(int k = 0; k <= j + 1; k++)
                A[i][k] -= A[j][k] * val / M[j] * C[i + 1][j];
        for(int j = 0; j <= i + 1; j++)
            A[i][j] += val * C[i+1][j];
        A[i][0] -= val * 1;
        long long g = M[i];
        for(int j = 0; j <= i + 1; j++)
            g = __gcd(g, llabs(A[i][j]));
        M[i] /= g;
        for(int j = 0; j <= i + 1; j++)
            A[i][j] /= g;
    }
}
/*
find sigma(i^2)
(i + 1)^3 - (i)^2 = 3*(i)^2 + 3i + 1
=> i^2 = 1/3 * ((i + 1)^3 - (i)^2 - 3i - 1)
=> sigma(i^2) = sigma(1/3 * ((i + 1)^3 - (i)^2 - 3i - 1))
=>            = 1/3 (sigma((i + 1)^3 - (i)^2) + sigma(-3i - 1)) 
=> // sigma((i + 1)^3 - (i)^3) = (n + 1)^3 - 1
=>            = 1/3 ((n + 1)^3 - 1 + sigma(-3i - 1)) 
... so
 */
int main() {
    init();
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%lld", M[n]);
        for(int i = n + 1; i >= 0; i--)
            printf(" %lld", A[n][i]);
        puts("");
        if(testcase)
            puts("");
    }
    return 0;
}