let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2007 QBMARKET - Siêu thị may mắn

solution.md

Gọi \(f_i\) là số cách mua cho tổng số tiền là \(i\), ban đầu \(f_0 = 1\). Ta duyệt qua mỗi mặt hàng, cập nhật lại \(f\) như sau:

\[f'_i = f_i + f_{i-c} + f_{i-2c} + f_{i-3c} + ... + f_{i-mc}\]

Với \(c\), \(m\) là giá và số lượng của mặt hàng đang xét.

Đặt

\[\Delta_i = f'_i - f_i = f_{i-c} + f_{i-2c} + f_{i-3c} + ... + f_{i-mc}\]

Ta thấy rằng \(\Delta_i = f_{i-c} + \Delta_{i-c} - f_{i-(m+1)c}\), vì vậy ở mỗi bước ta có thể tính \(\Delta\) trong \(O(s)\) rồi cập nhật lại \(f\) trong \(O(s)\).

Độ phức tạp thuật toán: \(O(ns)\).

Cần chú ý là kết quả có thể vượt giới hạn số 64-bit. Bản cài đặt ở dưới sử dụng số 128-bit để tính toán.

main.cpp
Open in Github • Download 
#include <cstdio>
#include <vector>
using namespace std;
#define UL unsigned long long
#define BASE 1000000000000000000ull
struct BigInt { UL h, l; };
const BigInt zero = {0, 0};

void operator += (BigInt &a, const BigInt b) {
    a.l += b.l;
    if (a.l > BASE) a.l -= BASE, a.h += 1;
    a.h += b.h;
}
void operator -= (BigInt &a, const BigInt b) {
    if (a.l < b.l) a.l += BASE-b.l, a.h -= 1;
    else a.l -= b.l;
    a.h -= b.h;
}
void print(BigInt a) {
    if (a.h == 0) printf("%llu", a.l);
    else printf("%llu%018llu", a.h, a.l);
}

int main() {
    int s, n;
    scanf("%d%d", &s, &n);

    vector<BigInt> f(s+1, zero), d(s+1, zero);
    f[0].l = 1;
    for (int k=0; k<n; k++) {
        int c, m;
        scanf("%d%d", &c, &m);

        for (int i=c; i<=s; i++) {
            d[i] = f[i-c];
            d[i] += d[i-c];
            if (i >= c*(m+1)) {
                d[i] -= f[i-c*(m+1)];
            }
        }

        for (int i=0; i<=s; i++) f[i] += d[i], d[i] = zero;
    }

    print(f[s]);
    return 0;
}
Comments