Hướng dẫn giải của Bedao Regular Contest 05 - CCAKE


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Khi cắt chiếc bánh bằng ~X~ đường cắt ngang và ~Y~ đường cắt dọc, dễ thấy rằng chiếc bánh này sẽ được chia thành ~X + 1~ phần theo chiều ngang và ~Y + 1~ phần theo chiều dọc.

Mỗi miếng bánh được cắt ra đều có diện tích ~\ge S~, vì vậy nếu như ta coi phần bé nhất được cắt ra theo chiều ngang là ~i~, thì tất cả phần được cắt ra theo chiều dọc phải ~\ge j = \lceil \frac{S}{i} \rceil~. Dựa vào điều này, ta có đáp án là tổng của ~3~ trường hợp sau:

  • ~i \ge \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
  • ~i < \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
  • ~i \ge \lceil \sqrt{S} \rceil, j < \lceil \sqrt{S} \rceil.~

Ở trường hợp ~1~, ta tính trực tiếp đáp án trong ~\mathcal{O}(1)~. Ở trường hợp ~2~, ta lặp qua tất cả các giả trị của ~i < \lceil \sqrt{S} \rceil~. Ở trường hợp ~3~, ta lặp qua tất cả các giả trị của ~j < \lceil \sqrt{S} \rceil~.

Do đó, ta đã chuyển được bài toán trở về hai bài toán con như sau:

  • Chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~.
  • Chia ~n~ số thành ~a~ số có giá trị bé nhất là ~b~.

Với bài toán đầu tiên, dễ thấy được đây là bài toán chia kẹo điển hình, với công thức là ~\binom{n - a \times (b - 1) - 1}{k - 1}~.

Với bài toán thứ hai, ta nhận thấy rằng đáp án là số cách chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~, trừ đi số cách chia ~n~ số thành ~a~ số đều có giá trị ~> b~. Do đó ta sẽ dùng cách tính của bài toán thứ nhất để tìm đáp án của bài toán thứ hai.

Độ phức tạp thuật toán: ~\mathcal{O}(t \times \sqrt{S})~.

Code mẫu

#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define fid(i,a,b) for(int i=a;i>=b;i--)
#define getbit(x,i) ((x>>i)&1)
#define pii pair<int,int>
#define ll long long
#define TunaNgoo "solution"
#define maxn 1000005
using namespace std;
const int mo = 1e9 + 7;
int T, N, M, X, Y, S;
ll fact[maxn * 2], po[maxn * 2], res;
int power(int a, int b)
{
    if(b == 0) return 1;
    ll c = power(a, b / 2);
    c = (c * c) % mo;
    if(b % 2) c = (c * a) % mo;
    return c;
}
int calc(int u, int v)
{
    if(u < 0) return 0;
    v--;
    u += v;
    return fact[u] * po[v] % mo * po[u - v] % mo;
}
int tg, k;
void solve()
{
    cin >> N >> M >> X >> Y >> S;
    X++;
    Y++;
    res = 0;
    k = sqrt(S - 1) + 1;
    res = (res + 1ll * calc(N - X * k, X) * calc(M - Y * k, Y)) % mo;
    fi(i, 1, k - 1)
    {
        tg = (S - 1) / i + 1;
        if(1ll * M >= 1ll * Y * tg) res = (res + 1ll * (calc(N - X * i, X) - calc(N - X * (i + 1), X)) * calc(M - Y * tg, Y)) % mo;
        if(1ll * N >= 1ll * X * tg) res = (res + 1ll * calc(N - X * tg, X) * (calc(M - Y * i, Y) - calc(M - Y * (i + 1), Y))) % mo;
    }
    res = (res + mo) % mo;
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen(TunaNgoo".inp", "r", stdin);
    freopen(TunaNgoo".out", "w", stdout);
    #endif // ONLINE_JUDGE
    fact[0] = 1;
    fi(i, 1, 2e6) fact[i] = (fact[i - 1] * i) % mo;
    po[2000000] = power(fact[2000000], mo - 2);
    fid(i, 2e6 - 1, 0) po[i] = (po[i + 1] * (i + 1)) % mo;
    cin >> T;
    while(T--)
    {
        solve();
        cout << '\n';
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.