티스토리 뷰

알고리즘 관련/BOJ

BOJ)11560 다항식 게임

JASON 자손9319 2017. 8. 1. 15:37

문제: 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
TAG
댓글
댓글쓰기 폼