#P8869. [2023省队模拟]行列式

    ID: 8963 传统题 3000ms 512MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>动态规划线性代数与代数高斯消元CF2400数学树形DP矩阵

[2023省队模拟]行列式

行列式

题目描述

给定 n×nn\times n 矩阵 A=(ai,j)A=(a_{i,j}),求 det⁡(A)\det(A) 模 109+710^9+7。矩阵由下列参数定义:

$$a_{i,j}=\begin{cases} b_j,&i=p_j,\\ c_i,&j=p_i,\\ d_i,&i=j,\\ x,&\text{其他情况}。 \end{cases}$$

其中 d1,…,dnd_1,\ldots,d_n 为对角线元素,pi,bi,ci (2≤i≤n)p_i,b_i,c_i\ (2\le i\le n) 和常数 xx 给定,且 pi<ip_i<i。

输入格式

第一行一个正整数 nn 和非负整数 xx。

第二行 nn 个非负整数 d1,…,dnd_1,\ldots,d_n。

接下来 n−1n-1 行,第 i−1i-1 行给出 pi,bi,ci (2≤i≤n)p_i,b_i,c_i\ (2\le i\le n)。

输出格式

输出行列式模 109+710^9+7。

补充样例输入

2 1
2 3
1 4 5

补充样例输出

999999993

矩阵为 (2453)\begin{pmatrix}2&4\\5&3\end{pmatrix},行列式为 −14-14。

补充样例 2

3 1
1 2 3
1 4 5
2 6 7
999999968

矩阵为 (141526173)\begin{pmatrix}1&4&1\\5&2&6\\1&7&3\end{pmatrix},行列式为 −39-39。

数据范围

全部数据满足 $1\le n\le10^6,\ 0\le b_i,c_i,d_i,x\le10^9,\ 1\le p_i<i$。

子任务 分值 限制
1 20 n≤300n\le300
2 15 pi=1,n≤105p_i=1,n\le10^5
3 25 x=0,n≤105x=0,n\le10^5
4 40 无