LQDOJ Cup 2025 - Round #3

Dạo gần đây, phòng Quan hệ Công chúng có báo cáo lại với ban Giám đốc của công ty Ma-tê rằng, người dùng Facenote (một mạng xã hội của công ty) đang phàn nàn rất nhiều về các lỗi vặt và trải nghiệm mà ứng dụng này mang lại. Sau khi phân tích, ban Giám đốc nhận thấy vì công ty mới thành lập, giai đoạn thành lập công ty còn thiếu vốn, nên các lập trình viên được thuê về vẫn còn non kinh nghiệm. Nay ngân sách công ty đã dồi dào, ban Giám đốc quyết định ra lệnh cho phòng Nhân sự thực hiện hai việc; đó là sa thải các lập trình viên không đủ năng lực, và tuyển thêm các lập trình viên mới.

Trong số các vị trí bị thay thế, có một vị trí nằm ngay trong ban Giám đốc là Giám đốc Kỹ thuật. Công ty nhận được hồ sơ của \(n\) ứng viên ứng tuyển cho vị trí này. Các ứng viên được đánh số ngẫu nhiên bởi các số nguyên từ \(1\) tới \(n\). Nhân vật chính của chúng ta hôm nay, anh Hùng, là ứng viên mang số (báo danh) \(1\)!

Vào ngày phỏng vấn, có \(l\) ứng viên tập trung tại công ty. Tất cả \(l\) ứng viên này đều nằm trong số \(n\) người đã nộp hồ sơ kể trên, tuy nhiên có thể có những ứng viên dù đã nộp hồ sơ nhưng lại không đến phỏng vấn. Số báo danh của \(l\) ứng viên này lần lượt là \(a_1, a_2, \ldots, a_l\). Trong đó ứng viên có số báo danh \(a_1\) là người đến sớm nhất, ứng viên có số báo danh \(a_2\) đến sớm thứ hai, \(\ldots\), ứng viên có số báo danh \(a_l\) đến muộn nhất.

Ban Giám đốc cảm thấy tuyển dụng theo quy tắc 36% hơi lâu nên đã bí mật quyết định như sau:

• Đầu tiên, ban Giám đốc chọn ứng viên ưng ý nhất là \(a_1\).
• Tiếp theo, các ứng viên lần lượt vào phỏng vấn theo thứ tự: ở lượt phỏng vấn thứ \(i\), ứng viên \(a_i\) sẽ được phỏng vấn. Nếu ban Giám đốc thấy ứng viên này ấn tượng hơn ứng viên ưng ý nhất ở thời điểm hiện tại, ứng viên ưng ý nhất sẽ được thay đổi thành \(a_i\). Ngược lại, ứng viên ưng ý nhất sẽ giữ nguyên như thời điểm trước đó.
• Do thời gian phỏng vấn có hạn, công ty ra luật nhằm rút gọi thời gian buổi phỏng vấn như sau: Nếu ở một thời điểm nào đó, sau \(k\) lượt phỏng vấn liên tiếp mà ứng viên ưng ý nhất vẫn không đổi, ban Giám đốc sẽ kết thúc buổi phỏng vấn và trao cơ hội cho người này. Các ứng viên còn lại sẽ ra về với lời nhắn: "Bạn rất tốt nhưng chúng tôi rất tiếc. Chúc bạn may mắn lần sau."

Với lợi thế có người quen đang làm ở ban Giám đốc Ma-tê, Hùng được tiết lộ rằng, thực ra số báo danh của các ứng viên không hề ngẫu nhiên! Qua phân tích hồ sơ, công ty đã ngầm đánh số các ứng viên theo quy tắc: ứng viên có năng lực càng tốt sẽ được đánh số càng nhỏ. Và khi phỏng vấn, ứng viên với số báo danh nhỏ hơn chắc chắn sẽ gây ấn tượng tốt hơn với ban Giám đốc. Điều đó có nghĩa là một khi Hùng (người mang số báo danh \(1\)) đã được phỏng vấn, chắc chắn Hùng sẽ được tuyển dụng!

Đêm trước ngày phỏng vấn, vốn là một người ne-vờ-thinh-kinh, Hùng trằn trọc suy nghĩ: chắc chắn mình phải đến rồi, nhưng không biết những người kia ai đến ai không, và họ sẽ đến sớm hay muộn ra sao đây? Rõ ràng, việc Hùng đến quá trễ vẫn có thể khiến Hùng bị loại vì luật "dừng phỏng vấn sau \(k\) lượt" kia, dù anh ta mới là người được đánh giá cao nhất. Hùng tưởng tượng ra nhiều kịch bản xếp hàng khác nhau, mỗi kịch bản lại là một chỉnh hợp của \(n\) ứng viên, và tất nhiên trong chỉnh hợp đó phải có Hùng. Cụ thể hơn:

• Mỗi kịch bản xếp hàng là một danh sách \(a\) gồm \(l\) số nguyên \((a_1, a_2, \dots, a_l)\) thỏa mãn các điều kiện sau:
  • với mọi vị trí \(i\), \(1 \leq a_i \leq n\).
  • tồn tại một vị trí \(j\) sao cho \(a_j = 1\).
  • các số nguyên \(a_1, a_2, \ldots, a_l\) đôi một phân biệt.
• Hai kịch bản \(\alpha = (\alpha_1, \alpha_2, \dots, \alpha_{\mu})\) và \(\beta = (\beta_1, \beta_2, \dots, \beta_{\nu})\) được gọi là khác nhau nếu:
  • \(\mu \neq \nu\); hoặc
  • tồn tại một vị trí \(\iota\) sao cho \(1 \leq \iota \leq min(\mu, \nu)\) và \(\alpha_{\iota} \neq \beta_{\iota}\).

Bây giờ đã là gần 7 giờ 22 phút sáng mà Hùng vẫn chưa ngủ, vì mải duyệt qua hết các kịch bản. Bạn đang nằm cạnh Hùng, muốn động viên Hùng đừng nghĩ nhiều mà nên chợp mắt một tí lấy sức trước phỏng vấn. Vì vậy, bạn hãy tính giúp Hùng số lượng kịch bản xếp hàng sao cho Hùng không được tuyển dụng, mặc dù anh ta là ứng viên xuất sắc nhất.

(Ghi chú: tác giả của kịch bản này có tên gồm đúng \(4\) tiếng, mỗi tiếng gồm đúng \(4\) chữ cái. Việc người này nằm cạnh Hùng là có mục đích gì, thì ban giám khảo chưa điều tra được. Chúng tôi sẽ tiếp tục điều tra về vụ việc này, và đưa đến cho quý vị những thông tin sớm nhất. Mong quý vị đón xem ở những tuần sau.)

Dữ liệu

Vào từ file văn bản recruitment.inp:

• Dòng đầu tiên chứa một số nguyên \(\tau\) là số bộ dữ liệu \((1 \leq \tau \leq 7)\).
• Tiếp theo là \(\tau\) dòng tương ứng với \(\tau\) bộ dữ liệu, mỗi dòng chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 3000^2)\).

Kết quả

Ghi ra file văn bản recruitment.out:

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là phần dư của số kịch bản khiến Hùng bị loại khi chia cho \(10^9 + 19972207\).

Ràng buộc

• Subtask \(1\) (\(6\) điểm): \(n \leq 5\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 10\)
• Subtask \(3\) (\(18\) điểm): \(n \leq 20\)
• Subtask \(4\) (\(10\) điểm): \(n \leq 80\)
• Subtask \(5\) (\(10\) điểm): \(n \leq 600\)
• Subtask \(6\) (\(14\) điểm): \(n \leq 4000\)
• Subtask \(7\) (\(8\) điểm): \(n \leq 70000\)
• Subtask \(8\) (\(10\) điểm): \(n \leq 300000\)
• Subtask \(9\) (\(16\) điểm): \(n \leq 9000000\)

Ví dụ

2
4 2
6 3

2
114

Thuở xa xưa, vương quốc Li Đốn Quê là một vương quốc hùng mạnh nằm gần bán đảo Tra Sờn. Sử sách ghi lại rằng vương quốc Li Đốn Quê được chia làm \(n\) ngôi làng nhỏ. Để thuận tiện cho việc quản lý, quốc vương đánh số các ngôi làng từ \(1\) đến \(n\). Các nhà sử học cũng tìm được một tấm bản đồ cổ và biết được rằng, \(n\) ngôi làng này được kết nối với nhau bởi \(n - 1\) con đường đất. Tất nhiên, mọi con đường đều là hai chiều và chúng đảm bảo rằng người dân có thể đi từ một ngôi làng bất kỳ tới tất cả các ngôi làng còn lại, thông qua một hoặc nhiều con đường.

Nhằm củng cố khả năng phòng thủ và đảm bảo quân đội luôn sẵn sàng trước các mối đe dọa từ ngoại bang, nhà vua tiến hành diễn tập chiến lược với \(q\) tình huống xâm lăng giả định. Các tình huống được đánh số từ \(1\) tới \(q\), và trong tình huống thứ \(j\), giả định rằng các ngôi làng có chỉ số từ \(l_j\) đến \(r_j\) đồng loạt bị tấn công bởi các thế lực ngoại xâm.

Để ứng phó, nhà vua phải tìm cách huy động quân đội đến các ngôi làng bị tấn công càng nhanh càng tốt. Đồng thời, việc di chuyển quân giữa các ngôi làng này cũng phải thuận tiện để các ngôi làng có thể hỗ trợ và bảo vệ lẫn nhau. Do đó, nhà vua cần xác định một vùng báo động chiến tranh. Vùng này sẽ bao gồm một số ngôi làng, đảm bảo được hai yếu tố. Thứ nhất, tất cả các ngôi làng bị tấn công đều phải nằm trong vùng báo động chiến tranh. Thứ hai, vùng báo động chiến tranh phải là một vùng liên thông, có nghĩa là nếu có hai ngôi làng cùng nằm trong vùng báo động chiến tranh, luôn tồn tại một cách di chuyển giữa hai ngôi làng này mà chỉ đi qua các ngôi làng thuộc vùng báo động chiến tranh.

Việc thiết lập chế độ thời chiến là điều nhà vua không hề mong muốn, bởi điều này gây ảnh hưởng tới đời sống sinh hoạt và sản xuất của người dân. Do đó, nhà vua luôn muốn số ngôi làng nằm trong vùng báo động chiến tranh là nhỏ nhất có thể.

Các bạn hãy giúp quốc vương xác định, với mỗi kế hoạch giả định, số ngôi làng tối thiểu nằm trong vùng báo động chiến tranh.

Dữ liệu

Vào từ file văn bản kingdom.inp:

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 50^3)\).
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n)\) cho biết có một con đường đất kết nối hai ngôi làng \(u_i\) và \(v_i\).
• Trong \(q\) dòng cuối cùng, dòng thứ \(j\) chứa hai số nguyên \(l_j\) và \(r_j\) \((1 \leq l_j \leq r_j \leq n)\) mô tả tình huống giả định thứ \(j\).

Kết quả

Ghi ra file văn bản kingdom.out:

• Gồm \(q\) dòng, dòng thứ \(j\) chứa một số nguyên là số ngôi làng tối thiểu thuộc vùng báo động chiến tranh trong tình huống giả định thứ \(j\).

Ràng buộc

• Subtask \(1\) (\(11\) điểm): \(n, q \leq 500\)
• Subtask \(2\) (\(11\) điểm): \(n, q \leq 2000\)
• Subtask \(3\) (\(17\) điểm): \(n \leq 2000\)
• Subtask \(4\) (\(19\) điểm): Mỗi ngôi làng có tối đa \(2\) con đường nối trực tiếp với các ngôi làng khác.
• Subtask \(5\) (\(23\) điểm): Tổng giá trị \(r_j - l_j\) trong các tình huống giả định không quá \(5 \cdot 10^5\).
• Subtask \(6\) (\(19\) điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

kingdom.inp

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

kingdom.out

4
2
3

Giải thích

Hình dưới đây mô tả các con đường ở vương quốc Li Đốn Quê trong ví dụ trên:

Ta có \(q = 3\) tình huống giả định như sau:

• \(l_1 = 1, r_1 = 3\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 1, 2, 3, 4\}\).
• \(l_2 = 3, r_2 = 4\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 3, 4\}\).
• \(l_3 = 4, r_3 = 5\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 2, 4, 5\}\).

Sau khi xuất sắc dành hạng \(24\) trong kỳ thi IOI 2015, kẻ-mà-ai-cũng-biết-là-ai-đấy quyết định tổ chức một bữa tiệc trà sữa chiêu đãi hết thảy bạn bè gần xa bà con khối phố. Kẻ-mà-ai-cũng-biết-là-ai-đấy đi đến quán trà sữa "ruột" của cậu ta và dự định mua \(k\) ly trà sữa về để chiêu đãi mọi người.

Quán trà sữa này có bán \(n\) món trà sữa khác nhau, được đánh số từ \(1\) tới \(n\). Có một điều đặc biệt về cửa hàng này là giá của các món trà sữa sẽ thay đổi sau mỗi lần mua. Cụ thể, ban đầu, giá một ly trà sữa loại \(i\) là \(i\) đồng. Tuy nhiên, mỗi khi kẻ-mà-ai-cũng-biết-là-ai-đấy mua một ly của loại nào, giá của chính loại đó sẽ tăng gấp đôi cho lần mua tiếp theo.

Ví dụ, khi kẻ-mà-ai-cũng-biết-là-ai-đấy mua ly trà sữa loại \(i\) đầu tiên, giá của ly này là \(i\) đồng. Sau đó, ly loại \(i\) tiếp theo có giá là \(i \cdot 2\) đồng. Nếu kẻ-mà-ai-cũng-biết-là-ai-đấy lại mua thêm một ly loại \(i\) nữa, ly thứ ba sẽ có giá là \(i \cdot 4\) đồng, và cứ thế tiếp tục.

Vào năm 2015, số tiền thưởng dành cho huy chương vàng Olympic Tin học quốc tế còn khá nhỏ (chỉ là \(15\) triệu đồng so với \(55\) triệu đồng ở thời điểm hiện tại), vì vậy kẻ-mà-ai-cũng-biết-là-ai-đấy muốn chi số tiền nhỏ nhất có thể. Các bạn hãy giúp kẻ-mà-ai-cũng-biết-là-ai-đấy chọn ra \(k\) ly trà sữa với tổng giá tiền nhỏ nhất nhé.

Dữ liệu

Vào từ file văn bản double.inp:

• Dòng đầu tiên chứa một số nguyên \(\tau\) \((1 \le \tau \le 2^{19})\) là số bộ dữ liệu.
• \(\tau\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\) \((1 \le n, k \le 2^{60})\) mô tả một bộ dữ liệu.

Kết quả

Ghi ra file văn bản double.out:

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là phần dư của tổng giá tiền nhỏ nhất của \(k\) ly trà sữa khi chia cho \(10^9 + 22071997\).

Ràng buộc

• Subtask \(1\) (\(10\) điểm): \(n, k \le 2^6\)
• Subtask \(2\) (\(20\) điểm): \(n \le 2^6\) và \(k \le 2^{14}\)
• Subtask \(3\) (\(25\) điểm): \(\tau \le 2^5\) và \(n \le 2^8\)
• Subtask \(4\) (\(25\) điểm): \(\tau \le 2^{13}\)
• Subtask \(5\) (\(20\) điểm): không có ràng buộc gì thêm.

Ví dụ

1
3 6

16