BOJ)11560 다항식 게임

문제: icpc.me/11560

문제를 풀기 위하여 k:0~20 에 대한 p(x)를 모두 구하여도 시간내에 충분히 수행가능하다.

따라서 미리 계산을 다 해준 뒤 쿼리를 받을 때 마다 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<vector<ll>> b, a;
ll x, y, z;
int main() {
    for (int i = 3; i <= 21; i++) {
        vector<ll> t;
        for (int j = 0; j < i; j++)
            t.push_back(1);
        b.push_back(t);
    }
    vector<ll> s;
    s.push_back(1);
    s.push_back(1);
    a.push_back(s);
    for (int i = 0; i < b.size(); i++) {
        vector<ll> next;
        int l = a.size() - 1;
        next.assign(a[l].size() + i + 2, 0);
        for (int j = 0; j < b[i].size(); j++) {
            for (int k = 0; k < a[l].size(); k++) {
                next[j + k] += b[i][j] * a[l][k];
            }
        }
        a.push_back(next);
    }
    scanf("%lld", &x);
    while (x--) {
        scanf("%lld%lld", &y, &z);
        printf("%lld\n", a[y - 1][z]);
    }
    return 0;
}