矩阵(matrix)
题目描述
$A$ 是一个 $N \times N$ 的矩阵, $X$ 和 $B$ 均为长度为 $N$ 的列向量,已知 $A, B$ 并且 $AX \equiv B (\bmod{M})$ ,现在请支持两种操作:
将 $B_i$ 修改为 $v$ 。
求 $X$ 的值。为了减小输出量,只需要输出 $\sum_{i=1}^{n} X_i*i \bmod{M}$ 。
输入格式
第一行两个正整数 $N, M, Q$ , $Q$ 为操作数量。
接下来 $N$ 行,每行 $N$ 个数,描述 $A$ 。
接下来 $1$ 行一共 $N$ 个数,描述 $B$ 。
接下来 $Q$ 行,每行若干个数描述一个操作,其中第一个数 $ty$ 表示操作类型。若 $ty=1$ 则表示为第一类操作,后有两个参数 $i, v$ ;若 $ty=2$ 则表示为第二类操作,后面没有参数。
输出格式
对于每个第二类操作输出一行一个整数,表示 $X_i$ 的值。
样例
输入
2 10007 3 1 1 0 1 3 2 2 1 1 4 2
输出
5 6
数据范围
$N \leq 300, Q \leq 50000, M \leq 10^9+7$ , $A$ 的行列式不为 $0$ ,$M$ 为质数。
Subtask1 ($30\%$) : $N \leq 50, Q \leq 100$ ;
Subtask2 ($20\%$) : $N \leq 100, Q \leq 1000$ ;
Subtask3 ($20\%$) : $N \leq 50, Q \leq 10000$ ;
Subtask4 ($30\%$) :无特殊限制。
时间限制: $2s$ 。
空间限制: $256MB$ 。