Anniversary Div 1 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

1. Tăng Giảm

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami ?có một dãy số nguyên $a$ gồm $N$ phần tử và một số $k$. Các bạn được làm thao tác sau không quá $m$ lần:

Chọn một cặp số $(i , j)$ thoả điều kiện $1 ≤ i, j ≤ N$ và $a[i] ≥ k$. Sau đó, gán $a[i] = a[i] - k$ và $a[j] = a[j] + k$.

Hãy tìm cách tận dụng thao tác trên để sau khi chuyển đổi, giá trị $max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])$ là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa một số nguyên dương $k$.
Dòng thứ hai chứa một số nguyên dương $m$.
Dòng tiếp theo chứa một số nguyên dương $N$.
$N$ dòng tiếp theo, mỗi dòng chứa một phần tử của $a$.

Output

$1$ số nguyên dương là kết quả bài toán. Giá trị nhỏ nhất của $max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])$.

Example

Test 1

Input

Output

Note

Ta không cần dùng thao tác nào. Sau đó, max(2 , 2 , 3) - min(2 , 2 , 3) = 1. Đây là giá trị nhỏ nhất có thể đạt được.

Test 2

Input

Output

Note

Ta sẽ áp dụng thao tác lên cặp (1, 3). Sau đó, dãy $a$ trở thành [3 3 3]. Max(3 , 3 , 3) - min(3 , 3 , 3) = 0. Đây là giá trị nhỏ nhất có thể đạt được.

Scoring

Subtask $1$: $70$% test có $N$, $m$ $\leq 50$ và 1 ≤ $k$ , $a[i]$ ≤ $10^9$.
Subtask $2$: $30$% test có $N$, $m$ $\leq 5 * 10^4$ và 1 ≤ $k$ , $a[i]$ ≤ $10^9$.

2. Đếm tập hợp

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho $n$ tập hợp $A_1,A_2,...,A_n$ biết rằng, tất cả các phần tử trong mỗi tập hợp đã cho đều thuộc đoạn $[1;m]$ và các phần tử trong mỗi tập hợp đều khác nhau từng đôi một !

Yêu cầu: Hỏi ta có thể tạo thành được bao nhiêu tập hợp khác nhau bằng cách lấy một vài tập hợp từ $n$ tập hợp đã cho hợp lại với nhau.

Input

Dòng thứ nhất chứa số $t(1\le t\le 50)$ - Thể hiện số testcase
$t$ block tiếp theo, mỗi block có dạng như sau:
- Dòng thứ nhất chứa hai số nguyên $n,m(1\le n\le 100,1\le m\le 14)$
- $n$ dòng tiếp theo, mỗi dòng gồm $k+1(k\le m)$ số nguyên trong đó: Phần tử đầu tiên thể hiện số lượng phần tử của tập hợp $A_i$ và $k$ phần tử tiếp theo - thể hiện các phần tử của tập $A_i$

Output

Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

Test 1

Input

Output

2
3

Note

Ứng với testcase 1, ta chỉ có thể tạo ra được 2 tập khác nhau đó là: $\left\{1\right\}$ ; $\left\{1,3\right\}$
Ứng với testcase 2, ta chỉ có thể tạo ra được 3 tập khác nhau đó là: $\left\{2,3\right\}$ ; $\left\{1,4\right\}$ ; $\left\{1,2,3,4\right\}$

3. Hiếu và bản đồ kho báu

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi thua cược nặng nề ở mùa Euro và quán bánh tráng trộn của NTHA, bồ của anh ta, thua lỗ nặng nề, zipdang04 đã không còn giàu có như trước nữa, giờ anh ta chỉ ở một ngôi nhà nhỏ và còn lại rất ít tiền để tiêu xài. Nhưng vì đang còn trong tuổi trai tráng, anh ta quyết định ra đi kiếm tiền để nuôi sống bản thân và ny của mình. Thương hoàn cảnh của anh ta, một ngày nọ có một vị tiên nhân xuất hiện và cho zipdang04 một kho báu có rất nhiều của cải quý giá. Vì muốn giàu nhanh nên anh ta đã lên đường đi đến nơi chôn giậu kho báu và định mang nó về. Nhưng khi đến nơi zipdang04 mới phát hiện ra kho báu bị khoá bởi 1 ổ khoá siêu hiện đại, và muốn mở nó thì phải biết dược mật khẩu của nó, nhưng vị tiên nhân kia quên nói cho anh ta.

Mật khẩu của kho báu là mỗi dãy số bao gồm các số từ $1$ đến $n$ và chưa biết trước độ dài, nên zipdang04 nghĩ rằng mình phải thử rất nhiều trường hợp mới mở được kho báu. Nhưng khi nhìn sang bên cạnh, anh ta thấy một bản đồ cho biết một số rằng buộc của mật khẩu. Bản đồ chứa $m$ cặp số $(u, v)$. Một mật khẩu hợp lệ nếu mọi cặp kề nhau trong mật khẩu đều thuộc $m$ cặp số trong bản đồ (có thứ tự).

Ví dụ: Nếu $n = 3$ và bản đồ chứa các cặp $(1, 2), (2, 3)$ thì:

$[1], [2], [3], [1, 2], [2, 3]$ là các mật khẩu hợp lệ
$[1, 2, 3]$ hợp lệ vì $(1, 2)$ và $(2, 3)$ đều có trong bản đồ
$[1, 3, 2]$ không hợp lệ vì cặp $(1, 3)$ không có trong bản đồ
$[3, 2]$ không hợp lệ vì $(3, 2)$ không có trong bản đồ

Nhưng đời đâu như mơ, lúc nhập mật khẩu, khi nhấn nút $i$ anh ta phải trả $a_i$ đồng để có thể nhấn được nút đấy, zipdang04 tự hỏi rằng trong trường hợp tệ nhất anh ta có thể mở được kho báu không. Bạn hãy tính giúp anh ấy số tiền trong trường hợp tệ nhất anh ấy phải bỏ ra nhé, vì con số này quá lớn nên hãy đưa ra mod $10^9 + 7$. Trường hợp tệ nhất là khi zipdang04 phải thử tất cả mật khẩu có thể. Nếu số lượng mật khẩu là vô hạn thì bạn hãy đưa ra $-1$

Input

Dòng đầu tiên là hai số $n$ và $m$ là số nút bấm và số cặp số.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, ..., a_n$, $a_i$ là số tiền phải trả khi bấm nút thứ $i$
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ miêu tả một cặp số trong bản đồ.

Output

Gồm một số nguyên duy nhất là kết quả của bài toán

Scoring

Subtask $1$ ($40\%$ số điểm): $n \leq 1000, m \leq 3000$
Subtask $2$ ($60\%$ số điểm): không có điều kiện gì thêm

Example

Test 1

Input

Output

Note

Trong ví dụ 1, các mật khẩu hợp lệ là:

+ $[1], [2], [3]$: tổng tiền là $1+2+3=6$
+ $[1, 2], [2, 3], [1, 3]$: tổng tiền là $12$
+ $[1, 2, 3]$: số tiền là $6$.
Như vậy tổng số tiền cần dùng là $6 + 12 + 6 = 24$.

Test 2

Input

Output

Note

Trong ví dụ 2, các mật khẩu hợp lệ là: $[1], [2], [3], [1, 2], [2, 3], [1, 2, 3]$

4. Tổng Riêng Biệt

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami có một dãy số $A$ gồm $n$ phần tử. Với một dãy số $B$, định nghĩa hàm $F(B)$ chính là số phần tử riêng biệt xuất hiện trong $B$. Hãy tính tổng $F(B)$ với $B$ là một dãy con liên tiếp của $A$.

Nói cách khác, hãy tính tổng $F([A_l, ..., A_r])$ với mọi cặp $1 \leq l \leq r \leq n$.

Ví dụ, $A = [1, 1, 2]$, ta sẽ có:

$F([1]) = F([1]) = F([2]) = F([1, 1]) = 1$
$F([1, 1, 2]) = F([1, 2]) = 2$.

Tổng tất cả các hàm $F$ sẽ là $1 * 4 + 2 * 2 = 8$

Nhiệm vụ của các bạn sẽ khó khăn hơn chút đỉnh. Bây giờ, dãy số sẽ được ami thay đổi $q$ lần. Mỗi lần, ami sẽ gán $a[i] = x$. Sau mỗi thay đổi như vậy, các bạn hãy tính tổng $F$ của dãy số $A$ mới.

Input

Dòng đầu tiên chứa 1 số nguyên dương $n$ là độ dài dãy $A$.
Dòng tiếp theo chứa $n$ số nguyên dương biểu thị dãy $A$.
Dòng tiếp theo chứa 1 số nguyên dương $q$ là số truy vấn.
$q$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương $i$ $x$ biểu thị một phép gán a[i] = $x$.

Output

$q$ dòng, mỗi dòng là một số nguyên dương tương ứng với tổng $F$ của dãy $A$ sau khi thực hiện các biến đổi.

Scoring

Trong tất cả các test , $1 \le i \le N$.

Subtask $1$ ($50\%$ số điểm): $N \leq 1000$, $x \le 20, a[i] \le 20$ và $q = 1$.
Subtask $2$ ($20\%$ số điểm): $N \leq 10^{5}$, $x \le 20$, $a[i] \le 20$ và $q = 1$.
Subtask $3$ ($30\%$ số điểm): $N \leq 10^{5}$, $x \le 10^5, a[i] \le 10^5$ và $q \le 10^5$.

Example

Test 1

Input

Output

20
17
13

Note

Sau truy vấn 1, dãy $A$ = [1 2 3 4].

F([1]) = F([2]) = F([3]) = F([4]) = 1
F([1 2]) = F([2 3]) = F([3 4]) = 2
F([1 2 3]) = F([2 3 4]) = 3
F([1 2 3 4]) = 4

Tổng các hàm F sẽ là 1 $ * $ 4 + 2 $ * $ 3 + 3 $ * $ 2 + 4 = 20

Sau truy vấn 2, dãy $A$ = [1 1 3 4].

F([1]) = F([1]) = F([1 1]) = F([3]) = F([4]) = 1
F([1 3]) = F([3 4]) = F([1 1 3]) = 2
F([1 1 3 4]) = F([1 3 4]) = 3

Tổng các hàm F sẽ là 1 $ * $ 5 + 2 $ * $ 3 + 3 $ * $ 2 = 17

Sau truy vấn 3, dãy $A$ = [1 1 1 4].

5. Chia nhóm

Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai dãy $a$ và $b$ gồm $N$ số nguyên, các phần tử của $b$ đôi một khác nhau. Ta tìm cách chia nhóm các phần tử của $a$, mỗi nhóm có ít nhất $2$ phần tử. Trong mỗi nhóm, số điểm đạt được là phần tử $a_i$ sở hữu $b_i$ cao thứ hai trong nhóm. Hãy tìm cách chia dãy $a$ thành các nhóm liên tiếp sao cho đạt được tổng số điểm của các nhóm là cao nhất.

Input

Dòng đầu tiên chứa số nguyên dương $N$ $(2\le n\le 3 * 10^5)$ thể hiện số phần tử trong hai dãy $a$ và $b$
Dòng thứ hai chứa n số nguyên $a_1, a_2, a_3, ..., a_n$. $(|a_i|\le 10^9)$
Dòng thứ hai chứa n số nguyên $b_1, b_2, b_3, ..., b_n$. $(|b_i|\le 10^9)$

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Subtask $1$ ($40\%$ số điểm): $N\le 1000$
Subtask $2$ ($60\%$ số điểm): không có điều kiện gì thêm

Example

Test 1

Input

5
1 2 3 5 4
1 5 3 2 4

Output

Note

Ở test ví dụ $1$, ta chia các phần tử thành $2$ nhóm. Nhóm $1$ gồm các phần tử $[1, 2, 3]$ và nhóm 2 gồm $[5, 4]$. Khi đó số điểm đạt được là $3 + 5 = 8$.

Test 2

Input

5
-3 4 -10 2 7
1 4 3 2 5

Output

Note

Ở test ví dụ $2$, phương án tối ưu nhất là chỉ gồm $1$ nhóm duy nhất. Khi đó số điểm đạt được là $4$

6. Kẻ nặng 10^7KG và đồ thị

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

tanprodium, người được mệnh danh là nặng $10^7$ $\text{kg}$ tại trường LQD đã thực hiện một phi vụ cực kỳ mạo hiểm, đó là trốn học lớp học của GSPVH cute. Tưởng rằng có thể một tay che trời, nhưng ngờ đâu, Flower_On_Stone đã phát hiện ra vụ việc này và rất tức giận. Flower_On_Stone quyết định dạy cho hắn một bài học nhớ đời. Để kiểm tra kiến thức lập trình của hắn, Flower_On_Stone đã ra 1 bài toán rất khó để đố hắn, và nếu không giải được thì tanprodium phải chịu phạt rất nặng. Nhưng vì hắn đang buồn vì tình nên không có tâm trí làm bài, mà lại không muốn chịu phạt nên tanprodium đã quyết định nhờ các bạn pro coder trên LQDOJ giải hộ. Là một pro coder, bạn hãy giải bài toán này giúp hắn nhé.

Cho một cây có $n$ đỉnh, mỗi đỉnh có một trọng số và hai số $a, b$. Hãy đếm số cặp $(u, v)$ mà $u \leq v$ sao cho tổng xor các đỉnh trên đường đi từ $u$ đến $v$ lớn hơn hoặc bằng $a$ và bé hơn hoặc bằng $b$.

Input

Dòng đầu tiên chứa số $n$ và hai số $a, b$
Dòng thứ hai chứa $n$ số nguyên $l_1, l_2 ... l_n$ trong đó $l_ì$ là trọng số của đỉnh thứ $i$
$n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ đại diện cho một cạnh của cây

Output

Gồm một dòng là kết quả bài toán

Constants

$n \leq 100000$
$1 \leq a,b,l_i \leq 10^9$
$1 \leq u, v \leq n$

Dữ liệu vào đảm bảo đồ thị là một cây

Scoring

Subtask $1$ ($25\%$ số điểm): $n \leq 5000$
Subtask $2$ ($25\%$ số điểm): Cây là một đường thẳng, các cạnh có dạng $(i, i+1)$ với $ 1 \leq i < n$
Subtask $3$ ($25\%$ số điểm): Cây là một cây nhị phân, các cạnh có dạng $(\lfloor{\dfrac{i}{2}\rfloor}, i)$ với $ 1 < i \leq n$
Subtask $4$ ($25\%$ số điểm): Giới hạn gốc, không có ràng buộc gì thêm.

Example

Test 1

Input

Output

7. Tính tổng với GCD

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

Cho số nguyên dương $n$. Tính $S=\sum\limits_{i=1}^{n}gcd(\left \lfloor{\sqrt[3]{i}}\right \rfloor ,i)$

Trong đó:

$gcd(a,b)$ - Thể hiện ước chung lớn nhất của hai số nguyên dương $a$ và $b$
$\left \lfloor{x}\right \rfloor$ - Thể hiện số nguyên lớn nhất và không vượt quá $x$ (với $x$ nguyên)

Input

Dòng thứ nhất chứa số $t(1\le t\le 10)$ - Thể hiện số testcase
$t$ dòng tiếp theo, mỗi dòng chứa số $n(1\le n\le 10^{21})$

Output

Ứng với mỗi testcase, in ra $S$ cần tìm. Vì $S$ có thể rất lớn, nên ta cần lấy mod $998244353$ trước khi in ra (Biết rằng: $998244353$ là số nguyên tố.)

Scoring

$10\%$ : $1\le n\le 100$
$10\%$ : $1\le n\le 1000000$
$20\%$ : $1\le n\le 10^{9}$
$30\%$ : $1\le n\le 10^{16}$
$30\%$ : Không có điều kiện gì

Example

Test 1

Input

Output

327
1069
522