Hướng dẫn cho PVHOI3 - Bài 5: Đề bài siêu ngắn

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: ngpin_04

Subtask 1:

Khi \(k = 1\) , mọi dãy số bất kì đều có bội số chung nhỏ nhất chia hết cho \(k\).
Đáp án là \((b - a + 1) ^ n\) vì mỗi phần tử \(x_i\) có \((b - a + 1)\) giá trị khác nhau

Code mẫu:

C++

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

const int mod = 998244353;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DEBAISIEUNGAN.inp","r",stdin);
    freopen("DEBAISIEUNGAN.out","w",stdout);
    long long n, k, a, b;
    cin >> n >> k >> a >> b;
    int ans = 1;
    while (n--) {
        ans = (long long) ans * ((b - a + 1) % mod) % mod;
    }
    cout << ans << "\n";
    return 0;
}

Subtask 2 và 3:

Subtask 2 và 3 được giải tương đối giống nhau, ta có nhận xét là \(n\) và \(b - a\) bé nên ta có thể duyệt trâu toàn bộ các dãy số \(x_i\) khác nhau trong độ phức tạp \(O((b - a) ^ n)\) sau đó tìm bội chung nhỏ nhất của dãy số
Tuy nhiên, một điểm đặc biệt ở subtask 3 chính là khi tìm bội chung nhỏ nhất của \(x_i\) có thể bị vượt giới hạn long long. Nhưng đề bài chỉ yêu cầu chúng ta tìm dãy số có bội chung nhỏ nhất chia hết \(k\) nên không cần phải lưu hoàn chỉnh bội chung nhỏ nhất mà chỉ lưu lại ước chung lớn nhất của nó với \(k\)

Code mẫu:

C++

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

const int mod = 998244353;

long long n,k,a,b;
long long prep[50];

int ans = 0;

void brute(int i, long long cur) {
    if (i > n) {
        ans += (cur == k);
        return;
    }
    for (long long x = a; x <= b; x++) {
        long long tmp = prep[x - a] // chi lay cac nhan tu cua k trong x
        long long nxt = cur / __gcd(cur, tmp) * tmp; // bcnn moi 
        brute(i + 1, nxt);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DEBAISIEUNGAN.inp","r",stdin);
    freopen("DEBAISIEUNGAN.out","w",stdout);
    cin >> n >> k >> a >> b;
    for (long long x = a; x <= b; x++) {
        prep[x - a] = __gcd(x, k); // chi lay cac nhan tu cua k
    }
    brute(1, 1);
    cout << ans << "\n";
    return 0;
}

Subtask 4:

Vì \(k\) là số nguyên tố nên chỉ cần một \(x_i\) chia hết cho \(k\) thì bội chung nhỏ nhất của dãy sẽ chia hết cho \(k\)
Vì thế, ta sẽ đếm số dãy \(x_i\) bất kì trừ đi cho số dãy \(x_i\) không tồn tại số chia hết cho \(k\)
Số lượng số chia kết cho \(k\) trong đoạn \([a, b]\) sẽ là \(\lfloor\frac{b}{k}\rfloor - \lfloor\frac{a-1}{k}\rfloor\)

Code mẫu:

C++

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

const int mod = 998244353;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DEBAISIEUNGAN.inp","r",stdin);
    freopen("DEBAISIEUNGAN.out","w",stdout);
    long long n, k, a, b;
    cin >> n >> k >> a >> b;
    int ans = 1;
    for (int i = 1; i <= n; i++)
        ans = (long long) ans * ((b - a + 1) % mod) % mod;
    // so day x_i bat ki

    int sub = 1;
    for (int i = 1; i <= n; i++) {
        long long notdivk = ((b - a + 1) - (b / k) + ((a - 1) / k));
        sub = (long long) sub * (notdivk % mod) % mod;
    }
    cout << (ans - sub + mod) % mod << "\n";
    return 0;
}

Subtask 5:

Nhận xét: nếu \(k\) có nhân tử là \(2^x\) và nhân tử của bội chung nhỏ nhất là \(2^y\) với \(y < x\) thì chúng ta không cần quan tâm đến \(2^y\) vì bội chung nhỏ nhất chỉ lấy số mũ lớn. Mỗi số nguyên tố chỉ có hai trường hợp là đã thỏa mãn hoặc chưa thỏa mãn.
Vì vậy chúng ta có thể tách \(k\) thành các số nguyên tố (\(2^x * 3^y * 5^z * \cdots)\), \(k\) không quá \(10^{14}\) nên số lượng số nguyên tố phân biệt không vượt quá 15
Ta sẽ có cách lưu bội chung nhỏ nhất bằng một dãy nhị phân \(mask\) với \(0/1\) cho ta biết số nguyên tố thứ \(i\) đã được thỏa mãn hay chưa
\(k\) và \(b\) bé hơn \(10^7\) nên ta sẽ tính \(mask\) của mỗi số \(i\) cho biết số i thỏa mãn những số nguyên tố nào. Sau đó đếm số lượng \(num[mask]\), số số nằm giữa \(a\) và \(b\) thỏa mãn \(mask\)

Cuối cùng là phần quy hoạch động bitmask không quá phức tạp.

C++

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int mod = 998244353;
const int N = 1e7 + 5;
vector <long long> p;

int dp[2][1 << 15];
int num[1 << 15];
int mask[N];

void add(int &a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("DEBAISIEUNGAN.inp","r",stdin);
    // freopen("DEBAISIEUNGAN.out","w",stdout);
    long long n, k, a, b;
    cin >> n >> k >> a >> b;
    for (int i = 2; (long long) i * i <= k; i++) {
        if (k % i == 0) {
            long long x = 1;
            while (k % i == 0) {
                k /= i;
                x *= i;
            }
            p.push_back(x);
        }
    }
    if (k > 1) {
        p.push_back(k);
    }

    for (int i = 0; i < (int) p.size(); i++) {
        int x = p[i];
        for (int j = x; j <= b; j += x) {
            mask[j] |= (1 << i);
        }
    }

    for (int i = a; i <= b; i++) 
        num[mask[i]]++;

    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        int cur = i & 1;
        int nxt = cur ^ 1;
        for (int x = 0; x < (1 << (int) p.size()); x++)
            dp[nxt][x] = 0;

        for (int x = 0; x < (1 << (int) p.size()); x++) 
        for (int y = 0; y < (1 << (int) p.size()); y++) {
            add(dp[nxt][x | y], (long long) dp[cur][x] * num[y] % mod) ;
        }
    }

    cout << dp[n & 1][(1 << (int) p.size()) - 1];
    return 0;
}

Subtask 6:

Chúng ta có thể tiếp tục tối ưu bằng cách sử dụng bao hàm loại trừ
Đầu tiên, ta sẽ xây dựng mảng \(cnt[mask]\) là số lượng số trong đoạn từ \(a\) đến \(b\) chia hết cho \(mask\) (tích các thừa số nguyên tố của \(k\) tương ứng với \(mask\)).
Gọi \(x\) là tích được tính từ \(mask\) vậy như subtask 4 "Số lượng số chia kết cho \(k\) trong đoạn \([a, b]\) sẽ là \(\lfloor\frac{b}{k}\rfloor - \lfloor\frac{a-1}{k}\rfloor\)"
Tuy nhiên trong số này còn chứa cả những số chia hết cho những mask khác hay nói cách khác là bội số của \(x\). Ví dụ: \(x = 2 * 3\) và \(k = 2 * 3 * 5\) vậy thì số lượng số chia hết cho \(x\) có thể bao gồm cả chia hết cho \(k\)
Vì vậy ta cần trừ đi các mask cha của chúng để đạt được \(cnt[mask]\) là những số chỉ chia hết cho \(mask\)
Tiếp theo ta có thể tính \(f[mask]\) là một dãy được tạo bởi các số chia hết cho tập con của \(mask\) bằng cách tính số lượng số là tập con của \(mask\) và luỹ thừa chúng cho \(n\).
Vì dãy được tạo bởi các số tập con của \(mask\) nên bội chung nhỏ nhất của chúng cũng là tập con của \(mask\) (hoặc có thể bằng \(mask\)). Ta chỉ cần trừ đi cho các tập con thì sẽ đạt được \(f[mask]\) là số dãy có bội chung nhỏ nhất chia hết đúng cho \(mask\)

C++

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int mod = 998244353;
const int N = 1e7 + 5;
vector <long long> p;

int f[1 << 15];
int dp[1 << 15];
long long cnt[1 << 15];
int mask[N];

int bit(int x) {
    return (1 << x);
}

int getbit(int x, int i) {
    return (x >> i) & 1;
}

void add(int &a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DEBAISIEUNGAN.inp","r",stdin);
    freopen("DEBAISIEUNGAN.out","w",stdout);
    long long n, k, a, b;
    cin >> n >> k >> a >> b;
    for (int i = 2; (long long) i * i <= k; i++) {
        if (k % i == 0) {
            long long x = 1;
            while (k % i == 0) {
                k /= i;
                x *= i;
            }
            p.push_back(x);
        }
    }
    if (k > 1) 
        p.push_back(k);

    int sz = p.size();
    for (int mask = 0; mask < bit(sz); mask++) {
        long long x = 1;
        for (int j = 0; j < sz; j++) 
            if (getbit(mask, j)) 
                x *= p[j];

        cnt[mask] = (b / x) - ((a - 1) / x);
    }

    for (int mask = bit(sz) - 1; mask > 0; mask--) {
        for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
            cnt[s] -= cnt[mask];
            if (s == 0)
                break;
        }
    }

    for (int mask = 0; mask < bit(sz); mask++)
        cnt[mask] %= mod;

    for (int mask = 0; mask < bit(sz); mask++) {
        add(dp[mask], cnt[mask]);
        if (mask == 0)
            continue;
        for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
            add(dp[mask], cnt[s]);
            if (s == 0)
                break;
        }
    }

    for (int mask = 0; mask < bit(sz); mask++) {
        f[mask] = 1;
        for (int i = 1; i <= n; i++) 
            f[mask] = (long long) f[mask] * dp[mask] % mod;
    }

    for (int mask = 1; mask < bit(sz); mask++)
    for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
        add(f[mask], mod - f[s]);
        if (s == 0)
            break;
    }

    cout << f[bit(sz) - 1];

    return 0;
}

Bình luận

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