Cho hai dãy số nguyên độ dài $n$, $B=[b_1,\ldots,b_n]$ và $C=[c_1,\ldots,c_n]$. Với một dãy số nguyên không âm độ dài $n$ là $D=[d_1,\ldots,d_n]$, gọi $S(D)$ là tập tất cả các chỉ số $i$ thỏa mãn $d_i=0$. Định nghĩa $f(D)=\sum_{i\in S(D)}b_i$, $g(D)=\prod_{i\in S(D)}c_i$. Đặc biệt, nếu $S(D)$ rỗng thì $f(D)=0$, $g(D)=1$.
小 L có một dãy số nguyên dương độ dài $n$, $A=[a_1,\ldots,a_n]$. 小 L có thể sửa dãy $A$ như sau:
- Chọn hai chỉ số kề nhau $i,j$ của dãy $A$ (tức là $1\le i,j\le n$ và $|i-j|=1$). Nếu $a_i\le a_j$, đổi $a_j$ thành $a_j-a_i$, đồng thời đổi $a_i$ thành $0$.
小 L có thể thực hiện bao nhiêu thao tác sửa đổi tùy ý, hoặc không sửa gì. Với tất cả các dãy $D$ có thể thu được từ $A$ bằng thao tác trên, 小 L muốn tìm giá trị lớn nhất của $f(D)$ và tổng các giá trị $g(D)$. Hãy giúp cậu tìm hai giá trị này. Hình thức hóa, gọi $T(A)$ là tập tất cả các dãy có thể thu được từ $A$ bằng thao tác trên, bạn cần tìm $\max_{D\in T(A)}f(D)$ và $\sum_{D\in T(A)}g(D)$. Vì $\sum_{D\in T(A)}g(D)$ có thể lớn, chỉ cần tìm phần dư của nó khi chia cho $1\,000\,000\,007$.
Dữ liệu vào
Đọc dữ liệu từ tệp sequence.in.
Bài toán có nhiều bộ dữ liệu kiểm thử.
Dòng đầu tiên chứa hai số nguyên không âm $c,t$, lần lượt biểu thị số hiệu bộ kiểm thử và số bộ dữ liệu kiểm thử. $c=0$ biểu thị bộ kiểm thử ví dụ.
Tiếp theo, lần lượt nhập từng bộ dữ liệu kiểm thử. Với mỗi bộ dữ liệu:
Dòng đầu tiên chứa một số nguyên dương $n$, biểu thị độ dài dãy.
Dòng thứ hai chứa $n$ số nguyên dương $a_1,\ldots,a_n$, biểu thị dãy $A$.
Dòng thứ ba chứa $n$ số nguyên $b_1,\ldots,b_n$, biểu thị dãy $B$.
Dòng thứ tư chứa $n$ số nguyên dương $c_1,\ldots,c_n$, biểu thị dãy $C$.
Dữ liệu ra
Ghi kết quả vào tệp sequence.out.
Với mỗi bộ dữ liệu kiểm thử, chỉ xuất một dòng chứa hai số nguyên, lần lượt biểu thị $\max_{D\in T(A)}f(D)$ và phần dư của $\sum_{D\in T(A)}g(D)$ khi chia cho $1\,000\,000\,007$. Chú ý: $\max_{D\in T(A)}f(D)$ không cần lấy môđun $1\,000\,000\,007$.
Bài toán gồm hai câu hỏi nhỏ; trả lời đúng bất kỳ câu nào đều được điểm thành phần. Quy tắc chấm cụ thể được cho trong phần Nhiệm vụ con.
Ví dụ
Dữ liệu vào 1
0 3 3 5 6 6 3 6 9 1 2 3 6 1 1 4 5 1 4 -1 1 -1 1 -2 2 1 1 1 1 1 1 8 4 2 4 2 2 2 4 4 -2 4 9 -3 4 8 7 8 1 1 1 1 1 1 1 1
Dữ liệu ra 1
15 10 1 18 37 48
Ghi chú
Ví dụ này gồm ba bộ dữ liệu kiểm thử.
Với bộ dữ liệu thứ nhất, có thể thu được 4 dãy sau:
- $D=[5,6,6]$, $f(D)=0$, $g(D)=1$;
- $D=[0,1,6]$, $f(D)=3$, $g(D)=1$;
- $D=[5,0,0]$, $f(D)=6+9=15$, $g(D)=2\times3=6$;
- $D=[0,0,5]$, $f(D)=3+6=9$, $g(D)=1\times2=2$.
Vì vậy, $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$, $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Ví dụ 2
Xem sequence/sequence2.in và sequence/sequence2.ans trong thư mục của thí sinh.
Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $3,4$.
Ví dụ 3
Xem sequence/sequence3.in và sequence/sequence3.ans trong thư mục của thí sinh.
Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $5,6$.
Ví dụ 4
Xem sequence/sequence4.in và sequence/sequence4.ans trong thư mục của thí sinh.
Ví dụ này thỏa mãn giới hạn của bộ kiểm thử $7$.
Ví dụ 5
Xem sequence/sequence5.in và sequence/sequence5.ans trong thư mục của thí sinh.
Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $11,12$.
Ví dụ 6
Xem sequence/sequence6.in và sequence/sequence6.ans trong thư mục của thí sinh.
Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $16\sim18$.
Giới hạn
Gọi $N$ là tổng các giá trị $n$ của mọi bộ dữ liệu kiểm thử trong một bộ kiểm thử. Với mọi dữ liệu kiểm thử, bảo đảm:
- $1\le t\le20$;
- $1\le n\le5\,000$, $N\le4\times10^4$;
- Với mọi $1\le i\le n$, $1\le A_i\le10^9$;
- Với mọi $1\le i\le n$, $-10^9\le B_i\le10^9$;
- Với mọi $1\le i\le n$, $1\le C_i\le10^9$.
| Số hiệu bộ kiểm thử | $n\le$ | $N\le$ | Tính chất đặc biệt |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Không có |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | Không có | ||
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | B | ||
| $11,12$ | Không có | ||
| $13$ | $3\,500$ | $3\times10^4$ | A |
| $14,15$ | B | ||
| $16\sim18$ | Không có | ||
| $19,20$ | $5\,000$ | $4\times10^4$ |
Tính chất đặc biệt A: bảo đảm $A_1=A_2=\cdots=A_n=1$.
Tính chất đặc biệt B: bảo đảm với mọi $1\le i\le n$, $A_i$ được sinh ngẫu nhiên đều và độc lập trong $[1,10^9]$.
Nhiệm vụ con
Với mỗi bộ kiểm thử:
- Trả lời đúng $\max_{D\in T(A)}f(D)$ cho tất cả các bộ dữ liệu kiểm thử sẽ được 40% số điểm;
- Trả lời đúng phần dư của $\sum_{D\in T(A)}g(D)$ khi chia cho $1\,000\,000\,007$ cho tất cả các bộ dữ liệu kiểm thử sẽ được 60% số điểm.
Chú ý: dù thí sinh chỉ trả lời một trong hai câu hỏi, vẫn phải xuất hai số nguyên theo định dạng dữ liệu ra, lần lượt tương ứng với đáp án của hai câu hỏi.