#P6925. 置换矩阵

    ID: 6756 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-行列式置换循环分解矩阵谱分解多项式除法模逆元快速幂多项式结式

置换矩阵

题目描述

给定长度为 nn 的序列 aa 和排列 pp。由它们构造一个 n×nn\times n 矩阵 AA。

$$A_{1,j}=a_j,\qquad A_{i,j}=A_{i-1,p_j}\quad(2\le i\le n).$$

求 det⁡(A)\det(A) 对 109+710^9+7 取模的结果。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,构成 1,2,…,n1,2,\ldots,n 的一个排列。

输出格式

输出一个整数,表示矩阵行列式对 109+710^9+7 取模后的非负余数。

样例

4
1 1 1 1
4 2 3 1
0
2
2 1
2 1
3

数据范围

1≤n≤50001\le n\le5000,1≤ai<109+71\le a_i<10^9+7。

原题子任务 附加限制 分值
1 n≤200n\le200 10
2 排列 pp 的环数大于 11 20
3 p1=np_1=n,且 pi=i−1p_i=i-1(i>1i>1) 30
4 无 40

原 PDF 题面

by Moonset