← 返回题目列表

AtCoder · agc047_d

D. 双二叉树

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

灵感来自电视剧 怪奇物语,熊利马克正在两个镜像世界之间散步。

有两棵高度完美的二叉树 H, 每个都有标准的顶点数 1 to 2^H-1。 根是 1 和孩子们 x 是 2 \cdot x 和 2 \cdot x + 1.

让 L 表示单棵树的叶子数量, L = 2^{H-1}.

给你一个排列 P_1, P_2, \ldots, P_L 数量 1 通过 L。 它描述了 L 特别 连接两棵树的叶子的边。 顶点之间有一条特殊的边 L+i-1 在第一棵树和顶点 L+P_i-1 在第二棵树中。

graph for sample1

第一个样本测试绘图,排列 P = (2, 3, 1, 4),绿色特殊边缘

让我们定义一下 产品 循环的 作为其顶点中的数字的乘积。 计算所有简单循环的乘积之和 恰好有两个特殊边缘,模数 (10^9+7).

简单循环是长度至少为 3、没有重复顶点或边的循环。

约束

  • 2 \leq H \leq 18
  • 1 \leq P_i \leq L 其中 L = 2^{H-1}
  • P_i \neq P_j (所以这是一个排列)

输入

输入由标准输入按以下格式给出(其中 L = 2^{H-1}).

H
P_1 P_2 \cdots P_L

输出

计算恰好具有两个特殊边的简单循环的乘积之和。 打印答案取模 (10^9+7).


示例输入 1

3
2 3 1 4

示例输出 1

121788

下图显示了产品的两个有效周期(但还有更多!) 2 \cdot 5 \cdot 6 \cdot 3 \cdot 1 \cdot 2 \cdot 5 \cdot 4 = 7200 和 1 \cdot 3 \cdot 7 \cdot 7 \cdot 3 \cdot 1 \cdot 2 \cdot 5 \cdot 4 \cdot 2 = 35280。 第三个循环无效,因为它没有恰好两个特殊边沿。

three cycles


示例输入 2

2
1 2

示例输出 2

36

图中唯一的简单循环确实有两条特殊边,顶点的乘积为 1 \cdot 3 \cdot 3 \cdot 1 \cdot 2 \cdot 2 = 36.


示例输入 3

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1

示例输出 3

10199246