#P10148. [2017备战wc]Y

    ID: 9204 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-矩阵谱分解矩阵求逆矩阵快速幂模逆元矩阵转置

[2017备战wc]Y

题目描述

给定一个 N×NN\times N 的上三角整数矩阵 MM 和正整数 KK。在模 998244353998244353 的意义下计算 MKM^K,将结果的每个元素表示为 [0,998244353)[0,998244353) 内的整数。求这些代表元的整数和与按位异或和。

输入矩阵的对角元在整数意义下两两不同且均非零。对角元取模后可能相等,也可能为零。

输入格式

第一行两个整数 N,KN,K。接下来 NN 行,每行 NN 个整数,按行给出矩阵。主对角线下方的元素均为 00。

输出格式

输出一行两个整数,依次为各元素的整数和及按位异或和。这两个最终结果直接输出。

2 1
1 0
0 2
3 3

数据范围

对于 40%40\% 的数据,1≤N≤1001\le N\le100,1≤K≤1091\le K\le10^9。对于全部数据,1≤N≤5001\le N\le500,1≤K≤1091\le K\le10^9。

原赛 PDF