{"problem":{"name":"数列前缀和 3","description":{"content":"给定模质数 $p$ 域上的 $k$ 阶非奇异矩阵列 $a$，给定 $q$ 次询问，每次给出 $l, r$，求 $\\prod \\limits_{i = l}^r a_i$。其中 $p = 1054^2 + 185^2$。容易证明这是一个质数。 注：模 $p$ 域上的非奇异矩阵指：矩阵乘法加法均在模 $p$ 下进行，矩阵（在实数域下）的行列式值对 $p$ 取余不为 $0$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3646"},"statements":[{"statement_type":"Markdown","content":"给定模质数 $p$ 域上的 $k$ 阶非奇异矩阵列 $a$，给定 $q$ 次询问，每次给出 $l, r$，求 $\\prod \\limits_{i = l}^r a_i$。其中 $p = 1054^2 + 185^2$。容易证明这是一个质数。\n\n注：模 $p$ 域上的非奇异矩阵指：矩阵乘法加法均在模 $p$ 下进行，矩阵（在实数域下）的行列式值对 $p$ 取余不为 $0$。\n\n## Input\n\n输入第一行有三个数，依次表示矩阵列长度 $n$、矩阵阶数 $k$ 以及询问数 $q$。\n\n接下来 $n \\times k$ 行，每行 $k$ 个整数，依次表示 $n$ 个 $k$ 阶矩阵，详见样例。\n\n接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。\n\n## Output\n\n为了避免输出过大，请输出一行一个整数，表示所有询问的答案的所有矩阵元素的按位异或和。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n$a_1 = \\begin{pmatrix} 2 & 2 & 3 \\\\ 4 & 5 & 6 \\\\ 7 & 8 & 9\\end{pmatrix}$，$a_2 = \\begin{pmatrix} 2 & 2 & 3 \\\\ 4 & 5 & 6 \\\\ 7 & 8 & 9\\end{pmatrix}$，$a_3 = \\begin{pmatrix} 20 & 20 & 21 \\\\ 22 & 23 & 24\n\\\\ 25 & 26 & 27\\end{pmatrix}$。\n\n$a_1 \\times a_2 = \\begin{pmatrix} 33 & 38 & 45 \\\\ \n70 & 81 & 96 \\\\\n109 & 126 &150 \\end{pmatrix}$，$a_2 \\times a_3 = \\begin{pmatrix}159 & 164 & 171 \\\\ 340 & 351 & 366 \\\\\n541 & 558& 582  \\end{pmatrix}$，$a_1 \\times a_2 \\times a_3 = \\begin{pmatrix}2621 &2704& 2820 \\\\   \n5582 & 5759 & 6006    \\\\\n8702 & 8978 & 9363    \\end{pmatrix}$。\n\n所有数字的按位异或和为 $14921$。\n\n### 数据规模与约定\n\n对于全部的测试点，保证 $1 \\leq n, q \\leq 10^6$，$2 \\leq k \\leq 3$，$1 \\leq l \\leq r \\leq n$，矩阵元素均为小于 $p$ 的正整数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3646","tags":["O2优化","前缀和","矩阵乘法","逆元"],"sample_group":[["3 3 3\n2 2 3\n4 5 6\n7 8 9\n2 2 3\n4 5 6\n7 8 9\n20 20 21\n22 23 24\n25 26 27\n1 2\n2 3\n1 3","14921"]],"created_at":"2026-03-03 11:09:25"}}