您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 766 Sum of Powers：冪和公式推導與二項式係數遞推

編輯：C++ 入門

問題描述

給定 k ≤ 20，將 S_k(n) = Σ_{i=1}^n i^k 化簡為 n 的多項式：a_{k+1} n^{k+1} + a_k n^k + ... + a_0，輸出係數（分數形式，已約分）。

數學推導

利用二項式定理：

(n+1)^{k+1} - n^{k+1} = Σ_{j=0}^k C(k+1, j) n^j
Σ_{i=1}^n [(i+1)^{k+1} - i^{k+1}] = (n+1)^{k+1} - 1
= Σ_{j=0}^k C(k+1, j) S_j(n)

遞推求解：

S_k(n) = [ (n+1)^{k+1} - 1 - Σ_{j=0}^{k-1} C(k+1, j) S_j(n) ] / C(k+1, k)

係數用分數 (num, den) 存儲，每步約分（gcd）。

參考代碼（C++）

#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 25;

ll C[N][N];
ll a[N][N]; // a[k][i] = S_k 中 n^i 的係數分子
ll m[N];    // m[k] = S_k 所有係數的公共分母

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

void reduce(ll &den, ll *num, int n) {
    ll d = gcd(den, llabs(num[0]));
    for (int i = 1; i <= n; i++) if (num[i]) d = gcd(d, llabs(num[i]));
    den /= d;
    for (int i = 0; i <= n; i++) num[i] = llabs(num[i]) / d * (num[i]>=0?1:-1);
}

void add(ll *p, ll *q, ll k, ll &den, ll f, int n) {
    for (int i = 0; i <= n; i++) p[i] = p[i]*f - q[i]*k*den;
    den *= f;
    reduce(den, p, n);
}

void init() {
    C[0][0] = 1;
    for (int i = 1; i < N; i++) {
        C[0][i] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[j][i] = C[j-1][i-1] + C[j][i-1];
    }
    memset(a, 0, sizeof(a));
    m[0] = 1; a[0][1] = 1; // S_0 = n
    for (int k = 1; k <= 20; k++) {
        int u = k+1;
        for (int j = 1; j <= u; j++) a[k][j] += C[j][u];
        m[k] = 1;
        for (int j = 0; j < k; j++)
            add(a[k], a[j], C[j][u], m[k], m[j], u);
        m[k] *= C[k][u];
        reduce(m[k], a[k], u);
    }
}

int main() {
    init();
    int T, k; scanf("%d", &T);
    while (T--) {
        scanf("%d", &k);
        printf("%lld", m[k]);
        for (int i = k+1; i >= 0; i--) printf(" %lld", a[k][i]);
        puts("");
        if (T) puts("");
    }
    return 0;
}