#PQJ1036x5031. QOJ 1036_5031

    ID: 2534 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2022-2023 集训队互测组合数学

QOJ 1036_5031

标题: 核 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

题目背景

shik 搞核工程去了。

题目描述

127 想要考考你解方程的能力。

你有这样一个方程:AB≡A(modq),其中 q 为素数,且满足 A,B 为 n 阶方阵,并且矩阵中的元素 ∈{0,1,2,...,q−1}(之后的所有矩阵也要满足这一点)。

方阵的同余 S≡T(modp) 被定义为 ∀i,j∈{1,2,...,n},Si,j≡Ti,j(modp),即对应位置同余。

对于这样的给定的 B,记 f(B) 表示使方程同余的所有 A 的数量。

但是给定一个 B 求解 f(B)太简单了,所以你需要对满足 |B|≠0(或者说可逆,非奇异)的 n 阶方阵求解 3f(B) 的和。

并且由于这个和太大了,你需要将这个和对一个给定的数 mod 取模。

注意,只有 n,q,mod 是给定的。

输入格式

第一行包含三个用空格隔开的正整数 n,q,mod。

输出格式

一行一个非负整数代表题面中的和对 mod 取模后的答案。

样例数据

样例 1 输入

2 2 1000000007

样例 1 输出

43046970

样例 1 解释

对于矩阵 B=(0110), 满足条件的 A 有: (0000),(0011),(1100),(1111), 共 4 个

对于矩阵 B=(0111), 满足条件的 A 有: (0000), 共 1 个

对于矩阵 B=(1001), 满足条件的 A 为所有的 A 共 16 个

对于矩阵 B=(1011), 满足条件的 A 有: (0000),(0010),(1000),(1010), 共 4 个

对于矩阵 B=(1101), 满足条件的 A 有: (0000),(0001),(0100),(0101), 共 4 个

对于矩阵 B=(1110), 满足条件的 A 有: (0000), 共 1 个

故答案为 34+31+316+34+34+31≡43046970(mod109+7)

样例 2 输入

100 127 998244353

样例 2 输出

881381862

样例解释二

的确如此

限制与约定

对于所有测试点,有 108≤mod≤109+7,2≤q<mod,且满足 q,mod 为素数

本题采用子任务捆绑测试,子任务描述及具体分值如下:

子任务 分值 n q mod 1 10 ≤3 ≤3 2 20 ≤102 3 10 ≤3⋅103 4 20 ≤106 =998244353 5 10 ≤107 =q+2 6 30