Editorial for Bedao Regular Contest 05 - CCAKE
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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'; } }
Comments