본문 바로가기

알고리즘 관련/BOJ

BOJ)11560 다항식 게임

문제: icpc.me/11560


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


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


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
#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 + 20);
        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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1514 자물쇠  (0) 2017.08.01
BOJ)5721 사탕 줍기 대회  (0) 2017.08.01
BOJ)11560 다항식 게임  (0) 2017.08.01
BOJ)10276 Jewelry Exhibition  (0) 2017.08.01
BOJ)1999 최대최소  (0) 2017.07.31
BOJ)13511 트리와 쿼리2  (0) 2017.07.31

태그