Bedao Grand Contest 15 - Sum^2 Xor

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
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~.

Comments

Please read the guidelines before commenting.


  • -7
    giga_hedgehog  commented on April 8, 2024, 5:26 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.