UOJ Logo

NOI.AC

#58. matrix

统计

矩阵(matrix)

题目描述

$A$ 是一个 $N \times N$ 的矩阵, $X$ 和 $B$ 均为长度为 $N$ 的列向量,已知 $A, B$ 并且 $AX \equiv B (\bmod{M})$ ,现在请支持两种操作:

  1. 将 $B_i$ 修改为 $v$ 。

  2. 求 $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$ 。