#P13042. [GCJ 2021 #3] Binary Search Game
[GCJ 2021 #3] Binary Search Game
题目描述
Alice and Bob are going to play the Binary Search game. The game is played on a board consisting of a single row of cells. Each cell contains an integer between 1 and , inclusive. There are also cards numbered 1 through . Before the game starts, the referee writes an integer between 1 and , inclusive, on each card, in one of the ways in which that can be done. Alice and Bob know the integers in the cells and on each card before they start playing.
The game proceeds alternating turns, with Alice having the first turn. There are turns in total, which means Alice plays turns and Bob plays turns. During a turn, a player can eliminate either the leftmost half or the rightmost half of the remaining cells. For example, let us consider a board that contains the numbers . In her first turn, Alice must choose to eliminate one half, leaving either or . If she eliminates the leftmost half and leaves , then Bob must choose between leaving and . If he were to leave , the game's final turn would have Alice choosing between and .
When the game is over, they look at the number in the only remaining cell. The score of the game is the integer written on card number . In the example above, if Alice were to eliminate and leave in her final turn, the score of the game would be the number the referee wrote on card number 2.
Alice plays optimally to maximize the score of the game, while Bob plays optimally to minimize it. They are given a fixed board with integers , , …, in its cells. For maximal fairness, they will play games, and the referee will choose a different way to write integers on the cards for each one. That means that for any given way of writing integers on the cards, Alice and Bob will play exactly one game with it. Given the game parameters and the fixed board contents, please determine the sum of the scores of all those games. Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime ().
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case consists of exactly two lines. The first line of each test case contains the three integers , , and . The second line contains integers , , …, , where is the integer contained in the -th cell from the left of the board.
输出格式
For each test case, output one line containing Case #x: y
, where is the test case number (starting from 1) and is the sum of scores of all games, modulo the prime ().
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
Case #1: 6
Case #2: 144
Case #3: 991661422
提示
Sample Explanation
In Sample Case #1, there are 4 ways to write the integers on the blank cards: , and . In the first two ways, no matter what Alice chooses in her first turn, Bob can always make the number in the last remaining cell be a 1, and card 1 contains a 1, which means those two games have a score of 1. In the last two ways, Alice can start by eliminating the leftmost half of the board, leaving for Bob, who then has no choice but to leave at the end. Since card 1 has a 2 on it in these ways, the score of both of these games is 2. The sum of all scores is therefore .
Limits
- .
- .
- , for all .
Test Set 1 (9 Pts, Visible Verdict)
- .
- .
Test Set 2 (26 Pts, Hidden Verdict)
- .
- .