2024.10.26 Problems - AlgoMaster Online Judge

Hệ số bậc k

Nộp bài

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: calkexp.inp Output: calkexp.out

Xét biểu thức sau: $(x + a)^n$ (với $a,n$ là số được cho).

Yêu cầu: Khai triển biểu thức trên, tính hệ số bậc $k$?

Input

Một dòng chứa ba số nguyên $a,n,k$ ($0 \le a \le 10^9; 1 \le n \le 2 \times 10^5; 0 \le k \le n$).

Output

Một dòng chứa một số nguyên duy nhất là kết quả bài toán, do kết quả có thể rất lớn, bạn cần đưa ra kết quả chia lấy phần dư cho $10^9+7$.

Scoring

Subtask $1$ ($25\%$ số điểm): $a = 1, n \le 10$.
Subtask $2$ ($25\%$ số điểm): $n \le 10$.
Subtask $3$ ($25\%$ số điểm): $a = 1$.
Subtask $4$ ($25\%$ số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

1 2 1

Output

Bài toán chia nhóm và những chú thỏ(*)

Nộp bài

Điểm: 5 Thời gian: 2.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Có $N$ con thỏ được đánh số $1,2,3,...,N$

Với mỗi $i,j(1\le i,j\le N)$, độ "tâm đầu ý hợp" của con thỏ $i$ và $j$ được kí hiệu bởi một số nguyên $a_{i,j}$. Ở đây $a_{i,i}=0$ với mọi $i(1\le i\le N),a_{j,i}=a_{i,j}$ với mọi $i,j(1\le i,j\le N)$.

$Kaninho$ chia $N$ con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác $1$ nhóm. Sau khi chia xong, với mỗi cặp $i,j(1\le i

Toán tử XOR

Nộp bài

Điểm: 4 (p) Thời gian: 4.0s Bộ nhớ: 1G Input: xorsegment.inp Output: xorsegment.out

Bạn được cho một mảng $a$ gồm $n$ số nguyên $a_1,a_2,...,a_n$. Bạn phải thực hiện $q$ truy vấn, có hai loại truy vấn:

"1 l r x": Sử dụng toán tử XOR với số nguyên $x$ lên tất cả các số nguyên trên đoạn từ $l$ đến $r$, nói cách khác: $a_i = a_i \oplus x \forall i: l \le i \le r$ ($1 \le l \le r \le n; 0 \le x \le 10^6$).
"2 l r": Tính tổng các số nguyên trên đoạn từ $l$ đến $r$, nói cách khác, đưa ra tổng: $a_l + a_{l+1} + ... + a_r$ ($1 \le l \le r \le n$).

Biểu thức $x \oplus y$ biểu diễn toán tử XOR của hai số nguyên $x$ và $y$.

Yêu cầu: Với mỗi truy vấn loại 2, đưa ra kết quả là một số nguyên trên một dòng.

Input

Dòng thứ nhất chứa hai số nguyên $n,q$ ($1 \le n,q \le 2 \times 10^5$).
Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,...,a_n$ ($0 \le a_i \le 10^6$).
$q$ dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên.

Output

Với mỗi truy vấn loại 2, đưa ra kết quả trên một dòng.

Scoring

Subtask $1$ ($20\%$ số điểm): $n,q \le 1000$.
Subtask $2$ ($20\%$ số điểm): mọi truy vấn loại 1 diễn ra trước mọi truy vấn loại 2.
Subtask $3$ ($20\%$ số điểm): mọi truy vấn loại 1 có $l = r$.
Subtask $4$ ($20\%$ số điểm): mọi truy vấn loại 1 có $x$ thuộc dạng $x = 2^k$ ($0 \le k < 20$).
Subtask $5$ ($20\%$ số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

5 8
4 10 3 13 7
2 2 4
1 1 3 3
2 2 4
2 3 3
1 2 5 5
2 1 5
1 1 2 10
2 2 3

Output