Hướng dẫn cho Truy vấn nhân chia

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: anhkha2003

Tóm tắt đề bài

Ban đầu có một số nguyên \(x = 1\) và một số nguyên dương \(M\). Có \(Q\) truy vấn thuộc hai loại:

1 val: Nhân \(x\) với \(val\).
2 pos: Chia \(x\) cho giá trị \(val\) đã được nhân ở truy vấn thứ \(pos\) (\(pos < i\), thao tác thứ \(pos\) là loại 1 và chỉ bị chia tối đa một lần).

Sau mỗi truy vấn, in ra giá trị \(x \bmod M\).

Phân tích

Ràng buộc: \(t \leq 5\), \(Q \leq 10^5\), \(M \leq 10^9\).
Khó khăn: Số \(M\) bất kỳ (không nhất thiết là số nguyên tố) và \(val\) có thể không nguyên tố cùng nhau với \(M\), do đó không thể sử dụng nghịch đảo modulo (modular inverse) để thực hiện phép chia.
Nhận xét quan trọng:
- Giá trị \(x\) tại bất kỳ thời điểm nào là tích của các giá trị \(val\) từ các truy vấn loại 1 chưa bị thao tác loại 2 hủy bỏ.
- Ban đầu, coi mỗi vị trí từ \(1\) đến \(Q\) có một hệ số bằng \(1\).
- Khi gặp truy vấn \(1\) tại bước \(i\) với giá trị \(val\), ta gán vị trí \(i\) có giá trị là \(val\).
- Khi gặp truy vấn \(2\) tại bước \(i\) với chỉ số \(pos\), việc "chia cho giá trị ở bước \(pos\)" tương đương với việc gán lại giá trị tại vị trí \(pos\) thành \(1\).
- Giá trị \(x \bmod M\) sau mỗi bước chính là tích của tất cả các phần tử từ \(1\) đến \(Q\) lấy dư cho \(M\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duy trì một mảng \(A\) có kích thước \(Q\), ban đầu tất cả các phần tử bằng \(1\).

Với truy vấn \(1\) ở bước \(i\): Gán \(A[i] = val\).
Với truy vấn \(2\) ở bước \(i\): Gán \(A[pos] = 1\).
Sau mỗi truy vấn, duyệt lại từ đầu mảng đến vị trí hiện tại \(i\), nhân dồn các phần tử và lấy dư cho \(M\).

Độ phức tạp

Thời gian: \(O(t \times Q^2)\), với mỗi truy vấn mất \(O(Q)\) để tính tích.
Không gian bộ nhớ: \(O(Q)\).
Đánh giá: Chỉ chạy được với Subtask 1 (\(Q \leq 500\)).

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int q;
    long long m;
    cin >> q >> m;
    vector<long long> a(q + 1, 1);

    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            long long val;
            cin >> val;
            a[i] = val % m;
        } else {
            int pos;
            cin >> pos;
            a[pos] = 1;
        }

        long long current_product = 1;
        for (int j = 1; j <= i; j++) {
            current_product = (current_product * a[j]) % m;
        }
        cout << current_product % m << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Python

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    num_test_cases = int(next(iterator))

    output = []
    for _ in range(num_test_cases):
        q = int(next(iterator))
        m = int(next(iterator))

        a = [1] * (q + 1)
        for i in range(1, q + 1):
            query_type = int(next(iterator))
            if query_type == 1:
                val = int(next(iterator))
                a[i] = val % m
            else:
                pos = int(next(iterator))
                a[pos] = 1

            cur = 1
            for j in range(1, i + 1):
                cur = (cur * a[j]) % m
            output.append(str(cur % m))

    print("\n".join(output))

if __name__ == "__main__":
    solve()

Hướng giải quyết (Tối ưu)

Nhận xét

Bài toán đưa về:

Cập nhật giá trị tại một vị trí (gán giá trị \(val\) hoặc gán lại \(1\)).
Tính tích toàn bộ mảng (hoặc tích đoạn \([1, Q]\)) theo modulo \(M\).

Cấu trúc dữ liệu Segment Tree (Cây phân đoạn) hoàn toàn phù hợp để thực hiện cả hai thao tác này trong thời gian \(O(\log Q)\) cho mỗi truy vấn.

Thuật toán

Xây dựng cây Segment Tree quản lý mảng có kích thước \(Q\). Mỗi nút quản lý đoạn \([l, r]\) sẽ lưu tích các phần tử trong đoạn đó modulo \(M\). Ban đầu mọi phần tử đều bằng \(1\).
Với mỗi truy vấn thứ \(i\):
- Nếu là loại 1 (1 val): Cập nhật giá trị tại vị trí \(i\) thành \(val \bmod M\).
- Nếu là loại 2 (2 pos): Cập nhật giá trị tại vị trí \(pos\) thành \(1\).
Sau khi cập nhật, kết quả của \(x \bmod M\) chính là giá trị tại nút gốc của Segment Tree (tương đương với tích trên đoạn \([1, Q]\)).

Độ phức tạp

Thời gian:
- Mỗi cập nhật trên Segment Tree mất \(O(\log Q)\).
- Với \(Q\) truy vấn, tổng thời gian cho một testcase là \(O(Q \log Q)\).
- Tổng thời gian cho \(t\) testcase là \(O(t \cdot Q \log Q)\), hoàn toàn chạy trong thời gian cho phép (\(10^5 \log_2(10^5) \approx 1.7 \times 10^6\) phép tính).
Bộ nhớ: \(O(Q)\) để lưu trữ cây Segment Tree.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

long long modulo;

struct SegmentTree {
    int size;
    vector<long long> tree;

    SegmentTree(int n) {
        size = n;
        tree.assign(4 * n + 1, 1 % modulo);
    }

    void update(int id, int left, int right, int pos, long long val) {
        if (left == right) {
            tree[id] = val % modulo;
            return;
        }

        int mid = (left + right) / 2;
        if (pos <= mid) {
            update(id * 2, left, mid, pos, val);
        } else {
            update(id * 2 + 1, mid + 1, right, pos, val);
        }

        tree[id] = (tree[id * 2] * tree[id * 2 + 1]) % modulo;
    }

    long long getProduct() {
        return tree[1] % modulo;
    }
};

void solve() {
    int q;
    cin >> q >> modulo;

    SegmentTree segmentTree(q);

    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            long long val;
            cin >> val;
            segmentTree.update(1, 1, q, i, val);
        } else {
            int pos;
            cin >> pos;
            segmentTree.update(1, 1, q, pos, 1);
        }

        cout << segmentTree.getProduct() << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Python

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    num_test_cases = int(next(iterator))
    output = []

    for _ in range(num_test_cases):
        q = int(next(iterator))
        mod = int(next(iterator))

        tree = [1 % mod] * (4 * q + 1)

        def update(node_id, left, right, pos, val):
            if left == right:
                tree[node_id] = val % mod
                return
            mid = (left + right) // 2
            if pos <= mid:
                update(node_id * 2, left, mid, pos, val)
            else:
                update(node_id * 2 + 1, mid + 1, right, pos, val)
            tree[node_id] = (tree[node_id * 2] * tree[node_id * 2 + 1]) % mod

        for i in range(1, q + 1):
            query_type = int(next(iterator))
            if query_type == 1:
                val = int(next(iterator))
                update(1, 1, q, i, val)
            else:
                pos = int(next(iterator))
                update(1, 1, q, pos, 1)

            output.append(str(tree[1] % mod))

    sys.stdout.write("\n".join(output) + "\n")

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.