Bedao Grand Contest 15 - Sum^2 Xor
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Xét mảng ~a~ gồm ~n~ phần tử. Gọi $$f(a) = \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} a_i \oplus a_j$$
Cho hai số ~n, m~ nguyên dương. Gọi ~S~ là tập các mảng ~a~ độ dài ~n~ thoả mãn ~0 \le a_i < 2^m~.
Tính ~\sum_{a \in S} f(a)~.
Input
Nhập một dòng duy nhất là hai số nguyên dương ~n, m~ (~2 \le n \le 10^5, 1 \le m \le 10^5~).
Output
In ra yêu cầu đề bài. Vì đáp án có thể rất lớn, in đáp án modulo ~998 \,244 \, 353~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~20\%~ | ~n \leq 8, m \leq 3~ |
| ~2~ | ~20\%~ | ~m = 1~ |
| ~3~ | ~20\%~ | ~n = 2~ |
| ~4~ | ~40\%~ | Không có ràng buộc gì thêm |
Sample Input 1
2 1
Sample Output 1
2
Notes
~f([0, 0]) = 0 \oplus 0 = 0~
~f([0, 1]) = 0 \oplus 1 = 1~
~f([1, 0]) = 1 \oplus 0 = 1~
~f([1, 1]) = 1 \oplus 1 = 0~
Đáp án là ~0 + 1 + 1 + 0 = 2~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.