Bài tập | NEU OJ

Cho ma trận vuông $A$ cấp $n$ với các phần tử nguyên, số nguyên không âm $k$ và số nguyên $p \ge 2$ . Dùng thuật toán lũy thừa nhanh (bình phương và nhân, nhân ma trận theo modulo $p$ ) để tính $A^k \bmod p$ , sau đó tính vết (trace) của $A^k$ theo modulo $p$ , tức tổng các phần tử trên đường chéo chính, lấy modulo $p$ .

Định dạng đầu vào:
Dòng 1: ba số nguyên $n\ k\ p$ . $n$ dòng tiếp theo, mỗi dòng $n$ số nguyên là ma trận $A$ .
Ràng buộc đầu vào:
$1 \le n \le 6$ , $0 \le k \le 10^{9}$ , $2 \le p \le 10^{9}$ , $|A_{ij}| \le 1000$ .
Định dạng đầu ra:
In ra một số nguyên duy nhất trong đoạn $[0,p-1]$ là vết của $A^k \bmod p$ .

solution

Đề bài: [Toán cho CNTT] Vết lũy thừa ma trận theo modulo