11500번: Polynomial

https://www.acmicpc.net/problem/11500

$O(Tt^2)$

Faulhaber's formula를 사용하는 문제
https://en.wikipedia.org/wiki/Faulhaber%27s_formula
$\sum k^p$을 n에 관한 다항식으로 미리 구해놓고 테스트 케이스마다 다항식들에 주어진 계수를 곱해서 더하면 된다.
다항식의 각 항의 계수에 쓰이는 기약분수의 사칙연산을 구현해야한다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll cb[27][27];
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int T, t, c[26];
struct frac {
    ll a, b;
    frac(ll _a = 0, ll _b = 1) : a(_a), b(_b) {}
    frac relax() {
        ll g = gcd(abs(a), b);
        return{ a / g,b / g };
    }
    frac operator + (frac x) const {
        return frac(a*x.b + x.a*b, b*x.b).relax();
    }
    frac operator - (frac x) const {
        return *this + frac(-x.a, x.b);
    }
    frac operator * (frac x) const {
        return frac(a*x.a, b*x.b).relax();
    }
}p[26][27];
int main() {
    for (int i = 0; i < 27; i++) {
        cb[i][0] = 1;
        for (int j = 1; j <= i; j++) cb[i][j] = cb[i - 1][j - 1] + cb[i - 1][j];
    }
    p[0][1] = frac(1);
    for (int i = 1; i < 26; i++) {
        for (int j = 1; j <= i + 1; j++) {
            frac u = frac(cb[i + 1][j]);
            for (int k = j - 1; k < i; k++) u = u - frac(cb[i + 1][k])*p[k][j];
            p[i][j] = u * frac(1, cb[i + 1][i]);
        }
    }
    for (scanf("%d", &T); T--;) {
        scanf("%d", &t);
        for (int i = 0; i <= t; i++) scanf("%d", c + i);
        ll tot = abs(c[0]);
        for (int i = 1; i <= t + 1; i++) {
            frac u;
            for (int j = i - 1; j <= t; j++) u = u + frac(c[j])*p[j][i];
            tot += abs(u.a);
        }
        printf("%lld\n", tot);
    }
    return 0;
}