#P9756. 游戏
游戏
题目描述
给定一个固定的数组 ,长度为 ,每个元素都在 中。另有一个长度为 的数组 ,每个位置填入 中的任意整数,共有 种填法。
对于每一种 的填法,wygz 和 ix35 轮流操作当前数组。每次将数组按位置切成等长的左右两半,丢弃其中一半并保留另一半,直到只剩下一个元素 。本局得分是 。
wygz 先手,希望得分尽可能大。ix35 希望得分尽可能小。双方都采用最优策略。求所有 种填法所得分数之和,对 取模。
输入格式
第一行一个正整数 ,表示数据组数。
对于每组数据,第一行三个正整数 ,第二行 个正整数,依次表示数组 的元素。
输出格式
每组数据输出一行一个整数,表示对应答案。
样例
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 | , | 30 |
| 2 | 20 | |
| 3 | ||
| 4 | 无 | 30 |