USACO 2015 - Tháng 2 - Hạng Vàng

Hôm nay, vì mải lo đi mua trà sữa cho crush mà Bảo Anh đến lớp muộn tận 30 phút. Thầy chủ nhiệm rất không hài lòng và phạt Bảo Anh phải nhảy lò cò quanh sân thể dục của trường. Sân thể dục là một lưới hình chữ nhật có kích thước \(N * M\) ô vuông và Bảo Anh phải nhảy từ ô \((1, 1)\) đến ô \((N, M)\) của sân trường. Thấy việc này quá dễ, Bảo Anh quyết định tăng độ khó cho thử thách. Bảo Anh đánh dấu nhãn các ô vuông bởi các giá trị nguyên có giá trị từ \(1\) đến \(K\) và cậu chỉ có thể nhảy từ ô hiện tại đến một ô khác nếu:

• Nhãn của ô cậu nhảy đến phải khác với nhãn của ô hiện tại.
• Ô mà cậu nhảy đến phải ở bên dưới ít nhất 1 hàng so với ô hiện tại.
• Ô mà cậu nhảy đến phải ở bên phải ít nhất 1 cột so với ô hiện tại.

Cảm thấy cũng chưa đủ khó, Bảo Anh muốn tính xem có bao nhiêu cách nhảy thỏa mãn khác nhau nếu cậu xuất phát từ ô \((1, 1)\) và kết thúc tại ô \((N, M)\). Tuy nhiên, vì đang bận tương tư nên Bảo Anh không thể tập trung giải quyết bài toán, bạn hãy giúp cậu ấy nhé.

INPUT

• Dòng đầu tiên gồm 3 số nguyên dương \(N, M, K\) \((2 \leq N, M \leq 750, 1 \leq K \leq N * M)\)
• \(N\) dòng tiếp theo chứa \(M\) số nguyên dương. Số thứ \(j\) của dòng \(i\) chứa số nguyên dương \(a_i,_j\) \((1 \leq a_i,_j \leq K)\)

OUTPUT

In ra số nguyên là số cách nhảy thỏa mãn khác nhau. Vì đáp số có thể rất lớn, nên bạn cần in kết quả khi chia lấy dư cho \(10^9 + 7\).

VÍ DỤ:

INPUT:

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

OUTPUT:

5

**Ràng buộc: **

• Subtask 1: \(\ 2 \leq N, M \leq 100\)
• Subtask 2: \(\ 2 \leq N, M \leq 750\)

Anh và Tiên là một đôi bạn thân. Nhân ngày sinh nhật của Tiên, Anh quyết định sẽ tặng cô bạn thân một món quà bất ngờ. Từ một nguồn tin thân cận, Anh biết rằng Tiên rất thích học tiếng Anh và các xâu kí tự đẹp, do đó Anh dự định sẽ mua tặng Tiên xâu kí tự mà cô bạn thích. Không may, sau khi mua xong Anh mới biết rằng Tiên cũng không thích một vài xâu kí tự xấu. Không muốn làm bạn mình buồn, Anh sẽ tạo ra một xâu kí tự mới từ xâu cũ mà không có các xâu kí tự xấu đó. Để làm được điều này, Anh sẽ làm như sau:

Anh đang có một xâu kí tự độ dài \(S\) và danh sách các từ xấu muốn xóa khỏi \(S\). Để làm điều này, Anh sẽ tìm lần xuất hiện đầu tiên của một xâu xấu \(T_i\) và xóa nó khỏi xâu \(S\), sau đó gộp 2 phần còn lại vào với nhau. Anh sẽ làm như thế cho đến khi trong xâu \(S\) không còn sự xuất hiện của bất kì xâu xấu \(T_i\) nào nữa. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một lần xuất hiện mới của một xâu xấu \(T_i\) mà trước đó không tồn tại. Anh còn biết rằng trong danh sách các xâu xấu sẽ không có xâu nào là xâu con của một xâu xấu khác. Có nghĩa là xâu xấu xuất hiện đầu tiên trong \(S\) ở mỗi thao tác là duy nhất.

Anh không biết rằng liệu xâu \(S\) cuối cùng sau khi thực hiện các thao tác có đủ đẹp để tặng Tiên không. Nếu xâu \(S\) đó không ưng ý thì Anh sẽ mua một xâu khác và thực hiện, thay vì bỏ thời gian ra để thực hiện với xâu cũ. Bạn hãy giúp Anh xác định xâu \(S\) cuối cùng sau khi thực hiện các thao tác là gì nhé.

Input:

• Dòng đầu tiên chứa xâu kí tự \(S\), là xâu ban đầu mà Anh có \((1 \leq |S| \leq 10^5)\)
• Dòng thứ hai chứa số nguyên dương \(N\), là số lượng xâu xấu có trong danh sách \((1 \leq N \leq 10^5)\)
• \(N\) dòng tiếp theo chứa xâu kí tự \(T_i\), là các xâu xấu trong danh sách \((1 \leq |T_i| \leq |S|)\). Tổng độ dài của \(N\) xâu \(T_i\) không quá \(10^5\)
• Các kí tự trong xâu \(S\) và \(T_i\) là các kí tự thường (từ \('a'\) đến \('z'\))

Output:

• In ra xâu \(S\) cuối cùng sau khi thực hiện thao tác. Dữ liệu đảm bảo rằng xâu \(S\) cuối cùng không rỗng.

Example

fromhanieutienwithlove
2
hieu
an

fromtienwithlove

Nông dân John cần bạn giúp quyết định vị trí xây một hàng rào có dạng đường thẳng nhằm hạn chế sự di chuyển của đàn bò. Ông đã cân nhắc một số vị trí có thể đặt hàng rào và cần bạn xác định những vị trí nào sử dụng được. Một hàng rào được coi là sử dụng được nếu tất cả các con bò đều nằm về cùng một phía của hàng rào. Hàng rào không sử dụng được nếu có một con bò nằm trực tiếp trên đó. Nông dân John sẽ đưa ra một số truy vấn về các vị trí có thể đặt hàng rào; một truy vấn phải được trả lời YES nếu nó tương ứng với một vị trí hàng rào sử dụng được, và NO nếu không.

Ngoài ra, đôi khi Nông dân John có thể đưa thêm bò mới vào đàn. Khi một con bò mới gia nhập đàn, trong tất cả các truy vấn hàng rào kể từ thời điểm đó, hàng rào chỉ được coi là sử dụng được nếu con bò mới nằm cùng phía với toàn bộ đàn bò còn lại.

Dữ liệu vào

Tệp fencing.in:

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)) và \(Q\) (\(1 \leq Q \leq 100\,000\)), cách nhau bởi một dấu cách. Đây lần lượt là số bò ban đầu trong đàn và số truy vấn.

\(N\) dòng tiếp theo mô tả trạng thái ban đầu của đàn bò. Mỗi dòng chứa hai số nguyên \(x\) và \(y\), cách nhau bởi dấu cách, biểu thị vị trí của một con bò.

\(Q\) dòng còn lại chứa các truy vấn, mỗi truy vấn hoặc thêm một con bò mới vào đàn, hoặc kiểm tra xem một hàng rào có sử dụng được hay không. Dòng có dạng 1 x y cho biết một con bò mới được thêm vào đàn tại vị trí \((x, y)\). Dòng có dạng 2 A B C cho biết Nông dân John muốn kiểm tra hàng rào được mô tả bởi đường thẳng \(Ax + By = C\).

Mọi vị trí bò đều phân biệt trên toàn bộ bộ dữ liệu và thỏa mãn \(-10^9 \leq x, y \leq 10^9\). Ngoài ra, các truy vấn hàng rào thỏa mãn \(-10^9 \leq A, B \leq 10^9\) và \(-10^{18} \leq C \leq 10^{18}\). Không truy vấn hàng rào nào có \(A = B = 0\).

Dữ liệu ra

Tệp fencing.out:

Với mỗi truy vấn hàng rào, in YES nếu hàng rào sử dụng được. Nếu không, in NO.

Ví dụ

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

YES
NO
NO

Cảnh báo: Lượng dữ liệu vào/ra của bài này khá lớn. Người dùng C++ có thể cân nhắc sử dụng scanf hoặc dòng lệnh ios_base::sync_with_stdio(false) để đọc dữ liệu nhanh hơn. Người dùng Java nên tránh sử dụng java.util.Scanner. Không xả bộ đệm đầu ra (chẳng hạn bằng std::endl) sau mỗi truy vấn.

Nguồn

USACO 2015 February Contest, Gold — Fencing the Herd

Tác giả bài: Richard Peng, 2015.