#PQJ1036x5031. QOJ 1036_5031
QOJ 1036_5031
标题: 核 - Problem - QOJ.ac
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