Bạn được cho hai dãy số nguyên $a_1, a_2, ..., a_n$ và $b_1, b_2, ..., b_m$. Bạn cần tạo ra một bảng $n \times m$ gồm các ô màu đen hoặc màu trắng, sao cho hàng thứ $i$ có đúng $a_i$ ô đen, và cột thứ $i$ có đúng $b_i$ ô đen.

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

00001
01011
00100
11100
-1

Bạn được cho một dãy $a$ có $n$ phần tử và bạn phải thực hiện hai loại truy vấn:

• Loại 1: ! u v: Thay đổi giá trị của $a_u$ thành $v$.
• Loại 2: ? l r: Giả sử mỗi thao tác bạn có thể chọn một phần tử bất kỳ và tăng nó lên 1 đơn vị, tính số thao tác ít nhất để dãy con từ $l$ đến $r$ trở thành dãy không giảm (lưu ý: đây chỉ là thao tác tính toán thuần túy, không ảnh hưởng đến dãy $a$).

Bạn còn được cho một số $t$, biểu thị độ phụ thuộc của các truy vấn loại 1. Nếu $t = 0$ thì các truy vấn loại 1 sẽ độc lập với nhau, hay nói cách khác, truy vấn loại 1 thứ $i - 1$ sẽ hết hiệu lực ngay trước khi thực hiện truy vấn loại 1 thứ $i$. Nếu $t = 1$, các truy vấn loại 1 sẽ cớ tác dụng vĩnh viễn.

4 0 6
2 4 1 4
! 2 4
? 1 4
! 3 3
? 1 4
! 2 1
? 1 4

3
1
2

5 1 6
2 10 4 2 5
? 3 5
! 3 3
? 3 5
! 2 4
! 4 6
? 1 5

2
1
2

Dữ liệu tài chính của một công ty trong $n$ ngày được biểu diễn bằng một dãy số $t_1,t_2,\dots,t_n$, trong đó $t_i\ (1\le i\le n)$ là lượng tiền thu về của ngày thứ $i$. Lãnh đạo công ty thường xuyên yêu cầu thống kê số liệu về tổng tiền lớn nhất thu được của hai ngày liên tiếp trong các ngày từ ngày $L$ đến ngày $R\ (L<R)$, nghĩa là cần tìm giá trị lớn nhất trong các giá trị $(t_i+t_{i+1})$ với $L\le i<R$.

Một nhân viên đã truy cập trái phép dữ liệu của công ty và trước mỗi lần lãnh đạo công ty yêu cầu thống kê số liệu, nhân viên sẽ tìm cách đảo ngược một đoạn dữ liệu nào đó trong các ngày từ ngày $L$ đến ngày $R$ với mục đích khi thống kê dữ liệu trong đoạn từ ngày $L$ đến ngày $R$ thì giá trị trả về càng lớn càng tốt. Vi dụ, nếu đảo ngược đoạn từ ngày $i$ đến ngày $j\ (1\le L\le i\le j\le R\le n)$ trên dữ liệu ban đầu $t_1,t_2,\dots,t_i,t_{i+1},\dots,t_j\dots,t_n$ thì dữ liệu thay đổi là $t_1,t_2,\dots,t_j,t_{j-1},\dots,t_i\dots,t_n$. Sau khi thống kê số liệu xong, người này sẽ lại thay đổi dữ liệu như ban đầu.

Yêu cầu: Cho biết dữ liệu ban đầu là $t_1,t_2,\dots,t_n$ và $q$ lần yêu cầu thống kê dữ liệu, hãy cho biết số liệu thống kê trả về khi bị can thiệp vào dữ liệu.

5 2
5 2 3 1 3
1 5
4 5

8
4

Cho mảng $A$ gồm $m$ phần tử (các phần tử được đánh số từ $1$ đến $m$) và mảng $B$ gồm $n$ phần tử (các phần tử được đánh số từ $1$ đến $n$), mỗi phần tử của hai mảng chỉ nhận một trong ba giá trị $-1,0,1$. Tiến hành tạo bảng $C$ kích thước $m\times n$, trong đó phần tử $(i,j)$ nhận giá trị $C[i][j]=A[i]\times B[j]$ với $1\le i\le m$ và $1\le j\le n$.

Một bảng con vuông kích thước $s$ của bảng $C$ có phần tử trái trên là $(x,y)$ và phần tử phải dưới là $(x+s-1,y+s-1)$ với $1\le x\le m-s+1$ và $1\le y\le n-s+1$ được gọi là bảng con vuông “cân bằng” nếu:

• Các phần tử thuộc đường chéo chính đều nhận giá trị bằng $1$. Cụ thể, các phần tử $(x,y),(x+1,y+1),\dots,(x+s-1,y+s-1)$ có giá trị bằng $1$.
• Tổng tất các các phần tử trong bảng con vuông bằng $0$.

Yêu cầu: Cho hai mảng $A$ và $B$, đếm số bảng con vuông “cân bằng” trong bảng $C$.

3 4
1 -1 1
1 0 -1 1

1

Vũ trụ $Z$ có $n$ hành tinh, các hành tỉnh được đánh số từ $1$ đến $n$. Một hệ thống gồm $m$ đường dịch chuyển, đường dịch chuyền thứ $k\ (1\le k\le m)$ sẽ giúp di chuyền từ hành tỉnh $i_k$ đến hành tinh $j_k$ và mất chi phí là $e(i_k,j_k)$. Một vụ nổ trong vũ trụ đã làm ảnh hưởng lớn đến tất cả các hành tinh, trừ hành tinh số $1$. Hành tinh số $1$ lên kế hoạch cứu hộ cho $n-1$ hành tinh còn lại.

Các nhà khoa học ở hành tinh số 1 đã tìm ra cách di chuyển giúp đội cứu hộ có thể di chuyển đến một hành tinh khác với chi phí nhỏ hơn. Cụ thể, với số nguyên không âm $a$ mà các nhà khoa học thiết đặt, giả sử đội cứu hộ lần lượt di chuyển qua dãy gồm $p$ hành tinh $1=x_1,x_2,\dots,x_p$. Như vậy, đội cứu hộ sẽ phải sử dụng $p-1$ đường dịch chuyển, gọi $s_1$ là tổng chi phí của $p-1$ đường dịch chuyển, gọi $r_1$ là tổng chi phí của $a$ đường dịch chuyền có chi phí lớn nhất trong $p-1$ đường dịch chuyển (nếu $a>p-1$ thì tính tổng chi phí của $p-1$ đường dịch chuyển), khi đó đội cứu hộ sẽ mất chi phí là $s_1-r_1$.

Về phía các hành tinh, các nhà khoa học cũng đã tính toán ra số nguyên không âm $b$ dựa trên mức độ ảnh hưởng của vụ nồ để xác định được chi phí di chuyển của cư dân. Cụ thể, nếu cư dân hành tinh $i$ phải di chuyển qua dãy gồm $q$ hành tinh $i=y_1,y_2,\dots,y_q$, gọi $s_2$ là tổng chi phí của $q-1$ đường dịch chuyển, gọi $r_2$ là tổng chi phí của $b$ đường dịch chuyển có chi phí nhỏ nhất trong $q-1$ đường dịch chuyển (nếu $b>q-1$ thì tính tổng chi phí của $q-1$ đường dịch chuyển), khi đó cư dân sẽ mất chi phí là $s_2+r_2$.

Chi phí để đội cứu hộ gặp được cư dân của hành tinh $i$ là tổng chi phí di chuyền của đội cứu hộ cộng với tổng chi phí của cư dân hành tinh $i$ di chuyển đề họ gặp được nhau.

Yêu cầu: Với mỗi hành tinh $i\ (2\le i\le n)$, hãy tính chi phí nhỏ nhất để đội cứu hộ xuất phát từ hành tinh $1$ có thể gặp cư dân của hành tỉnh $i$.

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

0 1 2

Dữ liệu tài chính của một công ty trong $n$ ngày được biểu diễn bằng một dãy số $t_1,t_2,\dots,t_n$, trong đó $t_i\ (1\le i\le n)$ là dữ liệu cho ngày thứ $i$, nếu $t_i\ge 0$ tức là ngày $i$ công ty thu về $t_i$ đồng, ngược lại $t_i<0$ tức là ngày $i$ công ty phải chi $|t_i|$ đồng. Lãnh đạo công ty thường thống kê số liệu về tổng thu chi của một dãy ngày liên tiếp mà có biến động lớn nhất, mức đánh giá biến động từ ngày $L$ đến ngày $R$ được tính bằng $|\sum_{i=L}^R t_i|$.

Một nhân viên đã truy cập trái phép dữ liệu của công ty trước khi lãnh đạo công ty thống kê số liệu, nhân viên đã thay đổi số liệu của một dãy các ngày liên tiếp từ ngày $u$ đến ngày $v\ (1\le u\le v\le n)$ một lượng $c$, cụ thể với ngày $i\ (u\le i\le v)$ giá trị $t_i$ được thay đổi bằng $t_i+c$. Sau khi thống kê số liệu xong, nhân viên này sẽ lại thay đổi dữ liệu như ban đầu.

Yêu cầu: Cho biết dữ liệu ban đầu là $t_1,t_2,\dots,t_n$ và $q$ giả định thay đổi số liệu, với mỗi giả định hãy cho biết giá trị $|\sum_{i=L}^R t_i|$ lớn nhất với $1\le L\le R\le n$.

5 2
1 -1 2 1 1
2 2 -2
2 4 -2

4
4

Cho một đồ thị có $2^n$ đỉnh được đánh số từ $0$ đến $2^n - 1$ và một dãy số nguyên $a_1, a_2, ..., a_m$. Tồn tại cạnh nối giữa đỉnh $i$ và $j$ khi và chỉ khi $i\ xor\ j = a_k$ với $1 \le k \le m$. Cho $q$ truy vấn, mỗi truy vấn gồm hai số nguyên $u, v$, nhiệm vụ của bạn là tìm độ dài đường đi ngắn nhất từ đỉnh $u$ đến đỉnh $v$.

3 2 4
5 3
1 7
3 5
1 5
0 3

2
2
-1
1

khanhphucscratch muốn tặng cho moi_hoc_code một món quà đặc biệt nhân ngày sinh nhật của bạn ấy, ngày 10 tháng 1 năm 2024. Vì không nghĩ ra được món quà nào đặc sắc nên khanhphucscratch chỉ đành tặng moi_hoc_code một chồng bài gồm $n$ là bài được đánh số từ $1$ đến $n$ theo thứ tự từ trên xuống dưới. Vì món quà chưa đủ ấn tượng, khanhphucscratch quyết định mời moi_hoc_code giúp mình thực hiện một thử thách. moi_hoc_code sẽ thực hiện $q$ lần tráo bài, mỗi lần cô sẽ rút $c_i$ các lá bài có thứ tự từ $l_i$ đến $l_i + c_i - 1$ từ trên xuống dưới và chèn chồng bài vào trên lá bài thứ $k_i$ trong số các lá bài còn lại (nếu $k_i = n - c_i + 1$ thì chồng bài sẽ được chèn vào dưới những lá bài còn lại). moi_hoc_code muốn khanhphucscratch xác định $t$ lá bài đầu tiên của chồng bài sau khi xáo.

5 5 2
3 2 2
3 3 1

4 2 5 1 3

khanhphucscratch và moi_hoc_code đang đứng ở hai đầu của một cầu thang gồm $m$ bậc, trong đó có $n$ bậc bị hỏng. khanhphucscratch đang ở bậc thang thứ nhất và muốn leo lên bậc thang thứ $m$. Trong mỗi bước, khanhphucscratch có thể leo lên không quá $k$ bậc (từ bậc $i$ có thể leo đến các bậc không quá $i + k$). Bạn hãy giúp khanhphucscratch đếm số cách leo đến bậc thứ $m$ nhé.

1 6 2
3

2

khanhphucscratch có một mảnh giấy hình chữ nhật kích thước $n \times m$ được chia thành các ô vuông đơn vị và muốn tính diện tích của tất cả các hình chữ nhật con (hình chữ nhật nằm gọn trong tờ giấy) có các cạnh song song với các cạnh của tờ giấy và bao trọn các ô vuông đơn vị. Thật không may, sau khi tính toán một vài phép tính cơ bản, khanhphucscratch nhận ra kết quả bài toán có thể rất lớn, nên muốn nhờ các bạn cùng tính để biết mình đúng hay sai. Các bạn hãy giúp khanhphucscratch nhé.

2
2 3
5 8

40
4200

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Dãy số $b$ được tạo bằng cách như sau:

• $b_1=a_1\oplus a_2$
• $b_2=a_2\oplus a_3$
• $b_3=a_3\oplus a_4$
• $\dots$
• $b_{n-1}=a_{n-1}\oplus a_n$
• $b_n=a_n\oplus a_1$

Trong đó, $\oplus$ là thao tác bit $XOR$. Bạn có thể đọc tại đây

Bạn được cho dãy số $b$, nhiệm vụ của bạn là tìm một dãy số $a$ thỏa mãn điều kiện sao cho thứ tự từ điển của dãy là nhỏ nhất.

Một dãy số $a$ được coi là có thứ tự từ điển nhỏ hơn dãy số $b$ khi tồn tại vị trí $i$ mà:

• Với mọi vị trí $j<i$ thì $a_j=b_j$
• $a_i<b_i$

3
3
1 2 3
3
1 0 0
10
3 6 4 5 2 4 5 14 1 8

0 1 3
-1
0 3 5 1 4 6 2 7 9 8

dbthuan208 đang rất thích tin học, đặc biệt là những bài toán về tập hợp các số nguyên. Nhận thấy được sở thích bạn mình, HoBaoPhuc2009 đã nghĩ ra một bài để thách thức bạn mình, đề bài như sau:

Ta gọi dãy số $a$ được gọi là dãy tăng nghiêm ngặt khi với mọi $1\le i<n$ thì $a_i<a_{i+1}$

Hai đoạn $[l,r]$ và $[u,v]$ được cho là không giao nhau khi không có giá trị $i$ nào thỏa mãn đồng thời $l\le i\le r$ và $u\le i\le v$

Yêu cầu: Cho một dãy số $a$ gồm $n$ phần tử, hãy chọn ra một số đoạn $[l,r]$ không giao nhau trong mảng $a$ sao cho khi đảo ngược tất cả các đoạn này trong dãy số (tức là biến đổi đoạn $a_l,a_{l+1},\dots,a_r$ thành $a_r,a_{r-1},\dots,a_l$) thì dãy số $a$ trở thành một dãy tăng nghiêm ngặt và số đoạn được chọn là ít nhất có thể.

dbthuan208 thấy đây là một bài toán quá khó đối với anh ấy, bạn có thể giúp anh ấy chứ?

10
3 2 1 6 5 4 9 8 7 10

3
1 3
4 6
7 9

weqd gọi 1 số là bình phương giai thừa nếu nó có thể được viết dưới dạng $(k!)^2$.

Bạn được weqd cho bạn 1 dãy số $a$ gồm $n$ số nguyên không âm và 1 số nguyên dương $k$. Nhiệm vụ của bạn là đếm số lượng dãy $p$ độ dài $k$ (không nhất thiết liên tiếp) thỏa mãn:

• $p$ là dãy con (không nhất thiết liên tiếp) của tập {$1,2,\dots,n$}
• Gọi $A=(a_{p_1}+a_{p_2})\times (a_{p_1}+a_{p_2}+a_{p_3})\times \dots \times(a_{p_1}+a_{p_2}+\dots+a_{p_k})$ và $B=(\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}})\times (\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}}+\frac{1}{a_{p_3}})\times \dots \times(\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}}+\dots+\frac{1}{a_{p_k}})$ thì $A\times B=(k!)^2$

Vì kết quả có thể rất lớn nên bạn hãy xuất kết quả sau khi $mod\ 10^9+7$

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

0
4
1

Bạn được cho một số nguyên dương $n<2^{20}$. Nhiệm vụ của bạn là tìm ba số nguyên dương $x,y,z<2^{20}$ bất kỳ sao cho $x\oplus y\oplus z=0$ và $x,y,z$ chia hết cho $n$, hoặc in ra ba số $-1$ nếu không có phương án.

1
5

80 90 10

Bạn được cho một ma trận tam giác bậc $n$. Cụ thể là ma trận sẽ có định dạng như sau:

Tại ô $(i,j)$ sẽ có giá trị là $a_{i,j}$. Bạn bắt đầu xuất phát từ đỉnh $(1,1)$. Mỗi lượt bạn có thể di chuyển đến ô $(i+1,j)$ hoặc ô $(i+1,j+1)$. Nhiệm vụ của bạn là tìm một đường đi từ ô xuất phát đến đích là bất cứ ô nào ở hàng $n$ sao cho tổng giá trị của tất cả các ô trên đường đi (tính cả ô xuất phát và kết thúc) là lớn nhất có thể

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

Một hôm nào đó, weqd đang làm toán. Thầy của anh ấy rất khó tính, nếu anh ấy làm sai 1 bài thì thầy lại cho anh ấy làm bài khó hơn. Vì lỡ tay viết nhầm dấu, nên kết quả bị sai, nên anh ấy bị thầy bắt làm 1 bài toán khó như sau:

Cho 6 số nguyên dương $x_1, x_2, y_1, y_2, z_1, z_2$. Nhiệm vụ của bạn là đếm số bộ ba số $(a; b; c)$ với $a, b, c$ thỏa mãn:

• $x_1\le a\le x_2$
• $y_1\le b\le y_2$
• $z_1\le c\le z_2$
• $a(a^2-bc)-b(ac-b^2)-c(ab-c^2)=0$

Đáng lẽ anh ấy có thể dùng điện thoại, nhưng máy điện thoại lại hết pin. Lúc này, bạn đang đem máy tính theo, bài này có thể giải nhanh hơn bằng máy tính, hãy giúp anh ấy.

1
3 4 4 4 4 5

1

Từ xa xưa, ba nước: TLE, VNOI, CF vẫn luôn phân vân và muốn biết xem nước nào là nước mạnh nhất về thể thao. Vì thế cả 3 nước đã quyết định tạo ra một thế vận hội “Olimpit Tam quốc” nhằm tìm ra xem nước nào là nước mạnh nhất. Cho đến ngày hôm nay, thế vận hội đã diễn ra được $t$ năm. Trong mỗi năm, các sự kiện sẽ được biểu diễn bởi một xâu $s$ chỉ gồm 3 ký tự là T,V,C. Trong đó, mỗi ký tự T tương ứng với việc nước TLE được thêm $1$ điểm, V tương ứng với VNOI và C tương ứng với CF. Đến cuối năm, nước nào được nhiều điểm nhất sẽ là nước vô địch năm đó (nếu có nhiều nước cùng nhiều điểm nhất thì ưu tiên theo thứ tự TLE > VNOI > CF)

Qua $t$ năm, ba nước muốn thống kê lại số lần vô địch của mỗi nước. Với trách nghiệm là 1 sứ giả, nhiệm vụ của bạn là đếm số lần vô địch của mỗi nước sau $t$ năm.

3
TCTVVCTTTVCT
TTVVCC
TCVCVCV

2 1 0

Hôm nay trên đường về nhà, Sayu-chan bỗng nghĩ ra một loại số mới và nó mang tên là số tuyệt vọng. Một số nguyên dương $N$ được gọi là số tuyệt vọng nếu nó chứa chính xác $K$ chữ số khác nhau.

Sayu-chan hiện tại cũng đang có hai số nguyên dương $L$ và $R$. Cô ấy muốn biết được tổng của các số tuyệt vọng trong đoạn $[L,R]$. Bạn hãy giúp Sayu-chan nhé.

2
10 34 1
24 513 2

66
37458

Bạn được cho một ma trận $n\times m$. Với mỗi ô $(i,j)$ trong ma trận có thể sẽ có giá trị $0$ hoặc $1$.

huyhau6a2 thực hiện 1 trò chơi trong ma trận như sau. Ban đầu bạn sẽ ở vị trí $(1,1)$. Từ ô $(i,j)$ bạn có thể đi đến 1 trong 2 ô $(i+1,j)\ (i<n)$ hoặc $(i,j+1)\ (j<m)$. Dễ dàng nhận thấy sau 1 số bước ta sẽ đến được ô $(n,m)$. Ta gọi giá trị của đường đi từ ô $(x_1,y_1)$ đến ô $(x_2,y_2)$ là tổng $XOR$ của tất cả giá trị trên đường đi (tính cả ô xuất phát và ô kết thúc).

Trong đó, $XOR$ là phép toán bit xor. Bạn có thể đọc tại đây

Với một ma trận kích thước $n\times m$, ta gọi ma trận đó là ma trận đẹp nếu với mọi đường đi hợp lệ từ ô $(1,1)$ đến ô $(n,m)$ thì giá trị của các đường đi đó đều bằng $1$

Nhiệm vụ của bạn là hãy đếm số cách điền các giá trị $0$ hoặc $1$ vào ma trận sao cho ma trận đó là ma trận đẹp. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 10^9+7$

3
1 1
1 2
2 2

1
2
4

1

10

01

10
00

00
01

01
10

11
11

Một cặp số nguyên dương $(i, j)$ được gọi là độc lập với nhau khi và chỉ khi $i\ \&\ j = 0$, trong đó $\&$ là phép toán thao tác bit AND.

Bạn được cho một dãy số nguyên dương $a$. Nhiệm vụ của bạn là đếm xem trong dãy có bao nhiêu cặp số độc lập.

8
1 2 3 4 5 6 7 8

13