#P9756. 游戏

    ID: 6382 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-阈值二值化容斥原理位集求并位计数交换求和顺序自然数幂和公式连续点值插值阶乘逆元预处理秦九韶算法

游戏

题目描述

给定一个固定的数组 aa,长度为 2L2^L,每个元素都在 [1,n][1,n] 中。另有一个长度为 nn 的数组 valval,每个位置填入 [1,m][1,m] 中的任意整数,共有 mnm^n 种填法。

对于每一种 valval 的填法,wygz 和 ix35 轮流操作当前数组。每次将数组按位置切成等长的左右两半,丢弃其中一半并保留另一半,直到只剩下一个元素 xx。本局得分是 valxval_x。

wygz 先手,希望得分尽可能大。ix35 希望得分尽可能小。双方都采用最优策略。求所有 mnm^n 种填法所得分数之和,对 109+710^9+7 取模。

输入格式

第一行一个正整数 TT,表示数据组数。

对于每组数据,第一行三个正整数 n,m,Ln,m,L,第二行 2L2^L 个正整数,依次表示数组 aa 的元素。

输出格式

每组数据输出一行一个整数,表示对应答案。

样例

3
2 2 2
2 1 1 1
4 3 2
3 1 1 4
5 100 3
2 4 1 1 4 5 2 5
6
144
991661422

第一组数据有四种填法 (1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2),对应得分分别为 1,1,2,21,1,2,2。

数据范围

对于全部数据,1≤T≤121\le T\le12,1≤L≤51\le L\le5,1≤ai≤n1\le a_i\le n,1≤m≤1091\le m\le10^9,1≤n≤321\le n\le32。

原题测试点 额外限制 分值
1 n≤8n\le8,m≤100m\le100 30
2 n≤15n\le15 20
3 n≤19n\le19
4 无 30

原 PDF 题面