Kỳ thi Bán kết OLP MT&TN lần 5 - năm 2024 - Bảng Chuyên Tin - Mirror

Với các tham số nguyên \(A\), \(B\), \(k\) cho trước, ta định nghĩa một dãy số nguyên dương là dãy đẹp nếu nó thỏa mãn các điều kiện sau:

• Có đúng \(2k\) phần tử (đánh chỉ số từ \(1\) đến \(2k\)).
• Tích của \(k\) phần tử đầu (có chỉ số từ \(1\) đến \(k\)) không vượt quá \(A\).
• Tích của tất cả \(2k\) phần tử đúng bằng \(B\).

Ví dụ: với \(A=4\), \(B=8\), \(k=2\) thì \([2, 2, 1, 2]\) là một dãy đẹp vì \(2\cdot 2=4\leq A\) và \(2\cdot 2\cdot 1\cdot 2=B\). Tương tự, \([1, 1, 1, 8]\) và \([1, 2, 1, 4]\) cũng là hai dãy đẹp. Ngược lại, \([4, 2, 1, 1]\) không phải là dãy đẹp vì \(4\cdot 2=8>A\).

Nhiệm vụ của bạn là lập trình tính số lượng dãy đẹp khác nhau ứng với từng input \(A\), \(B\), \(k\) được nhập vào. Hai dãy \(X\) và \(Y\) được coi là khác nhau nếu độ dài của chúng khác nhau, hoặc tồn tại một chỉ số \(i\) sao cho \(X_i\ne Y_i\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(1000000007\) (\(10^9+7\)).

Input

• Một dòng duy nhất chứa ba số nguyên dương \(A\), \(B\) và \(k\). (\(1\leq A\leq B\leq 10^9\), \(1\leq k\leq 10^5\))

Output

• Một số nguyên duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(A \leq B\leq 10\), \(k\leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(B\) là một lũy thừa của \(2\) và \(k\leq 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(B\) là một lũy thừa của \(2\) và \(k\leq 1000\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 8 2

16

4 8 4

100

Nhân dịp 8/3, Thuận đã lên kế hoạch mua quà cho bạn gái rất kĩ lưỡng. Trên đường đi tới nhà bạn gái, Thuận sẽ ghé ngang qua một số tiệm hoa, quà, trà sữa, v.v ... để mua những món quà mà cô ấy thích nhất, do đó anh đã cố định một tuyến đường đi. Hệ thống giao thông trong thành phố có thể mô hình hóa thành một đồ thị có \(n\) đỉnh, và \(m\) cạnh hai chiều, có trọng số. Dãy các địa điểm mà Thuận sẽ đi là \(s = s_1, s_2, s_3, \dots, s_k = t\) trong đó \(s\) là nhà Thuận, \(t\) là nhà của bạn gái, và có tổng cộng \(k\) địa điểm trên tuyến đường.
Trên chiếc xe Light (Full-Self Driving, không cần người lái) của Thuận được tích hợp phần mềm định vị VK Map. Thuận đã cung cấp điểm đến là \(t\) cho xe. Khi ở tại vị trí là đỉnh \(x\) bất kì trên đồ thị, VK Map sẽ xác định điểm \(y\) liền kề với \(x\) và thuộc đường đi ngắn nhất từ \(x\) tới \(t\) (cũng như toàn bộ phần còn lại của đường đi ngắn nhất tới \(t\)). Nếu kế tiếp, Thuận lựa chọn đi đến điểm \(z \neq y\), thì VK Map sẽ tính toán lại toàn bộ đường đi.
Là một kỹ sư đã thiết kế nên xe Light, Thuận rất quan tâm tới tốc độ xử lý và hiệu suất của phần mềm VK Map này. Thuận biết rõ, khi tồn tại nhiều đường đi ngắn nhất khác nhau cùng tới được \(t\), phần mềm sẽ gợi ý một tuyến bất kì. Nhưng hôm nay, khác với mọi khi, Thuận đã cố định sẵn lộ trình mà anh ấy sẽ đi là dãy \(s_1, s_2, \dots, s_k\), bất kể gợi ý của hệ thống. Anh ấy tò mò, liệu trong trường hợp tốt nhất, cũng như tệ nhất thì VK Map sẽ tính toán lại đường đi bao nhiêu lần?

Yêu cầu: Cho trước \(n,m,k\); mô tả hạ tầng giao thông của thành phố; tuyến đường Thuận dự định đi. Hỏi số lần tạo đường đi mới ít nhất, và nhiều nhất của VK Map là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq m \leq 4 \times 10^{5})\).
• \(m\) dòng tiếp theo, mõi dòng chứa ba số nguyên \(u, v, w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{9})\), thể hiện rằng có một con đường nối hai địa điểm \((u,v)\) với trọng số là \(w\).
• Dòng tiếp theo chứa số nguyên \(k\) \((1 \leq k \leq n)\).
• Dòng cuối cùng chứa \(k\) số nguyên \(s_1, s_2, \dots, s_k\) là chỉ số của \(k\) địa điểm sẽ đi qua

Output

• Ghi ra hai số nguyên là số lần tính toán lộ trình gợi ý tối thiểu và tối đa.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m,n \le 2000, w = 1\).
• Subtask \(2\) (\(25\%\) số điểm): \(m,n \le 2000\).
• Subtask \(3\) (\(25\%\) số điểm): \(w = 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

4 4
1 2 1
1 3 2
2 3 1
3 4 1
3
1 3 4

0 1

6 9
1 5 1
5 4 1
1 2 1
2 3 1
3 4 1
4 1 1
2 6 1
6 4 1
4 2 1
4
1 2 3 4

2 2

Thuận là chủ của thương hiệu Mountain Game - chuyên cung cấp dịch vụ leo núi dưới dạng một trò chơi thi đấu. Khu vực tổ chức thi leo núi của Mountain Game có thể được chia thành \(n\) cấp bậc với độ cao tăng dần. Trong đó, \(a_i\) là độ khó khăn để vượt từ cấp \(i-1\) lên cấp \(i\). Ta quy ước cấp \(0\) là mặt đất, nơi mỗi người chơi sẽ bắt đầu.
Theo luật chơi, nếu người chơi hiện đang có mức độ thể lực là \(x\), thì người đó chỉ vượt qua được những cấp bậc có độ khó không lớn hơn \(x\). Việc di chuyển lên các cấp không tiêu hao thể lực.
Sau khi đi tới cấp độ \(i\), bất kì người chơi nào cũng sẽ nhận được một buff hoặc nerf tương ứng, giúp thể lực của người đó giảm đi một lượng \(b_i\), tức là

(nếu \(b_i\) âm, tức thể lực của người chơi được tăng lên - buff). Ta giả sử có vô hạn buff / nerf tại mỗi cấp, nhưng mỗi người chơi khi tiến tới cấp \(i\) sẽ được nhận buff tại tầng đó một lần duy nhất.
Luật chơi cũng giới hạn người chơi di chuyển từ cấp thấp lên cấp cao hơn, lần lượt, tức từ cấp \(i\) lên cấp \(i+1\) theo thứ tự \(1,2,3,\dots,n\).
Ngoài ra, để đảm bảo an toàn, khi một người chơi không thể tiến thêm được nữa (không đủ thể lực hoặc đã ở cấp cuối cùng), trên mỗi cấp đã có bố trí sẵn phòng nghỉ ngơi và cánh cửa thần kì để mỗi người chơi dừng lại và trở về mà không tiêu hao thể lực.
Dĩ nhiên, khi vượt qua một màn với độ khó khăn là \(x\) thì người chơi cũng được thưởng thêm một lượng tiền là \(x\) USD. Phần thưởng này đã thu hút rất nhiều người chơi đăng ký.
Có \(q\) người chơi đã đăng ký Mountain Game, với mỗi người thứ \(j\), Thuận biết được thể lực của người đó là \(k_j\) (theo thông tin đăng ký). Để dự trù kinh phí, Thuận cần tính trước với mỗi người, tổng tiền thưởng cần chuẩn bị cho anh ta là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n,q \leq 5 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^9)\) là độ khó của các cấp độ.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n (|b_i| \le 10^9)\) là mức độ thay đổi thể lực của từng cấp.
• \(q\) dòng tiếp theo, dòng thứ \(j\) chứa một số \(k_j\) \((1 \leq k_j \leq 10^{15})\) là thể lực của người chơi thứ \(j\).

Output

• Với mỗi người chơi, in ra lượng tiền tối đa của người đó có thể được thưởng, trên một dòng riêng biệt.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(n,q \le 5000\).
• Subtask \(2\) (\(24\%\) số điểm): \(b_i = 0\).
• Subtask \(3\) (\(26\%\) số điểm): \(b_i < 0\).
• Subtask \(4\) (\(26\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
2 3 5
2 -1 1
1
2
5
8

0
2
5
10

Thuận rất thích chơi game, tuy nhiên hôm nay Thuận phải học toán. Vì thế, cậu ấy đã nghiên cứu một trò chơi toán học rất thú vị như sau. Xét băng giấy dài, thẳng gồm \(n\) ô vuông liên tiếp. Bắt đầu từ ô số \(1\), cậu sẽ lần lượt "nhảy" tới ô số \(n\) theo các quy tắc đã định sẵn.
Cậu đặt ra \(k\) quy tắc, mỗi quy tắc gồm một đoạn số \([l, r]\), tức là với mỗi số \(d\) mà \(l \le d \le r\), thì Thuận sẽ được phép nhảy từ ô số \(i\) sang ô số \(i+d\) (tất nhiên \(i+d \le n\)).
Là một cậu bé thông minh và có lòng hiếu kì khám phá những kiến thức mới lạ, Thuận đã thử liệt kê tất cả các cách khác nhau để "nhảy" từ ô \(1\) tới ô \(n\) theo những quy tắc trên, nhưng cậu không biết mình đã đếm đủ chưa. Do đó, Thuận cần các bạn lập trình để tính xem có bao nhiêu cách để nhảy từ ô số \(1\) tới ô số \(n\).
Để thuận tiện, Thuận đã xác định cách thức sau để phân biệt hai cách nhảy khác nhau bất kì từ ô \(1\) tới ô \(n\): Mỗi khi đứng tại một ô nào mới, Thuận sẽ viết thêm số hiệu của ô đó vào cuối dãy số. Dãy số thu được sau mỗi lần đi tới \(n\) sẽ đặc trưng cho một cách nhảy riêng biệt.
Ví dụ, với \(n = 4\), \(k = 1\) và \(l_1 = 1, r_1 = 2\), có thể tồn tại những cách nhảy sau:

• \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 2 \rightarrow 4\)

Lưu ý, vì kết quả có thể rất lớn nên hãy in ra phần dư của nó sau khi chia cho \(10^9 + 7\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \le 5 \times 10^{5}, 1 \le k \le 50)\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i (1 \le l_i \le r_i \le n)\) biểu thị cho một quy tắc

Output

• Gồm một dòng duy nhất chứa số cách đếm được, khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(n \le 5000, k = 1\).
• Subtask \(2\) (\(16\%\) số điểm): \(n \le 5000, k = 2\).
• Subtask \(3\) (\(18\%\) số điểm): \(n \le 5000\).
• Subtask \(4\) (\(16\%\) số điểm): \(k = 1\)
• Subtask \(5\) (\(16\%\) số điểm): với \(i \neq j\) bất kì, luôn có \(\min(r_i, r_j) < \max(l_i, l_j)\)
• Subtask \(6\) (\(18\%\) số điểm): không có ràng buộc gì thêm.

Example

7 1
2 4

4