Editorial for Bedao Mini Contest 17 - DIVISORS
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhận xét:
Với mọi số nguyên tố ~p~, gọi ~p_x~, ~p_y~, ~p_z~ lần lượt là số mũ của cơ số ~p~ trong phân tích thừa số nguyên tố của ~X~, ~Y~ và ~Z~, ta có ~p_y \leq p_z \leq p_x~. Bên cạnh đó, tổng các ~p_z~ (với mọi số nguyên tố ~p~) không vượt quá ~k~.
Lưu ý: các giá trị ~p~ không xuất hiện trong phân tích thừa số nguyên tố của ~X~ thì xem như ~p_x = 0~, tương tự với ~p_y~ và ~p_z~.
Với mỗi số nguyên tố ~p~, xem ~p_y, p_x~ như một cặp số ~(l, r)~, bài toán chuyển về như sau:
Có ~n~ cặp số ~(l, r)~, với mỗi cặp ~(l_i, r_i)~ cần chọn một số nguyên trong đoạn ~[l_i;r_i]~ sao cho tống các số được chọn không vượt quá ~k~.
Lưu ý, ta chỉ quan tâm đến những cặp ~(p_y, p_x)~ mà ~p~ xuất hiện trong phân tích thừa số của ~X~ hoặc ~Y~, vì khi ~p~ không xuất hiện trong cả hai thì ~p_x = p_y = 0~, vậy ~p_z = 0~ và không ảnh hưởng đến tổng các số được chọn.
Trong trường hợp số tồn tại ~p_y > p_x~, đáp án chắc chắn bằng ~0~.
Trở lại với bài toán, ta sử dụng quy hoạch động để giải quyết, cụ thể như sau. Gọi ~dp[i][j]~ là số cách chọn ~i~ số cho ~i~ cặp ~(l, r)~ đầu tiên mà tổng ~i~ số đó bằng ~j~.
Ta có ~dp[i][j] = \sum_{k = max(0, j - r_i)}^{j - l_i} dp[i - 1][j]~ ~\forall j \geq l_i~.
Để tính nhanh được tổng trên có thể dùng tổng tiền tố.
Độ phức tạp của thuật toán là ~O(n \times q)~.
Code mẫu
//TrungNotChung #include <bits/stdc++.h> #define pii pair<int , int> #define fi first #define se second #define BIT(x,i) (1&((x)>>(i))) #define MASK(x) (1LL<<(x)) #define CNT(x) __builtin_popcountll(x) #define task "tnc" using namespace std; const int N = 110; const int K = (int)1e5+228; const int mod = (int)1e9+7; void add(int &x, const int &y) { x += y; if(x >= mod) x -= mod; } void sub(int &x, const int &y) { x -= y; if(x < 0) x += mod; } #define PRODUCT(x,y) (1LL*(x)*(y)%mod) int power(int x, int y) { int res = 1; while(y > 0) { if(1&y) res = PRODUCT(res, x); x = PRODUCT(x, x); y /= 2; } return res; } int n, m, k, a[N], p[N], b[N], q[N]; int need[N]; map<int, int> pos; int dp[N][K]; void solve() { cin >> k; cin >> n; for(int i=1; i<=n; ++i) cin >> a[i]; for(int i=1; i<=n; ++i) cin >> p[i], pos[p[i]] = i; cin >> m; for(int i=1; i<=m; ++i) cin >> b[i]; for(int i=1; i<=m; ++i) { cin >> q[i]; if(pos[q[i]] == 0) { cout << 0; return; } need[pos[q[i]]] = b[i]; } for(int i=1; i<=n; ++i) { if(a[i] < need[i]) { cout << 0; return; } } for(int i=0; i<=k; ++i) dp[0][i] = 1; for(int i=1; i<=n; ++i) { for(int j=0; j<=k; ++j) { if(j > 0) add(dp[i][j], dp[i][j-1]); int l = need[i], r = min(j, a[i]); if(l > r) continue; add(dp[i][j], dp[i-1][j-l]); if(j - r > 0) sub(dp[i][j], dp[i-1][j-r-1]); } } cout << dp[n][k]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }
Comments