#P6730. Guessing Game on the Blackboard
Guessing Game on the Blackboard
Guessing Game on the Blackboard
On a blackboard there are written n distinct positive integers \(a_1, a_2, \cdots, a_n\) all less than \(p\). Little J chooses one of the non‐empty subsets of these numbers uniformly at random, and then plays a number‐guessing game with Little M.
The rules of the game are as follows. At the beginning, Little J secretly picks a non‐empty subset \(X \subseteq \{a_1,a_2,\dots,a_n\}\). To figure out \(X\), Little M is allowed to make several queries. In each query, Little M may pick any number \(a_k\). If \(a_k \in X\) then Little J replies with all numbers in \(X\) that can be written in the form \[ (a_k)^m \bmod p\] for some positive integer \(m\) (note that modulo means the remainder after division). Otherwise, if \(a_k \notin X\), Little J simply replies that \(a_k\) is not chosen.
The game ends immediately once Little M has determined exactly which numbers Little J has chosen.
For example, suppose \(n=4\), \(p=7\) and the numbers written on the board in order are \(\{1, 3, 4, 6\}\). If Little J secretly picks \(X=\{1,4,6\}\) then one possible (not necessarily optimal) game is as follows:
| Little M's Query | Little J's Response |
|---|---|
| \(a_2 = 3\) | Little J replies that \(3\) is not chosen. |
| \(a_4 = 6\) | Little J replies: \(6 (=6^1\bmod7)\) and \(1 (=6^2\bmod7)\). |
| \(a_3 = 4\) | Little J replies: \(4 (=4^1\bmod7)\) and \(1 (=4^3\bmod7)\). |
After 3 queries, Little M has deduced exactly which numbers were chosen and the game ends.
Little M is in a hurry – he still has homework to finish – so he wants to evaluate the expected number of queries he must make using an optimal strategy. Let \(S\) denote the minimum expected number of queries required to determine \(X\) (when Little J picks \(X\) uniformly at random from the set of all non‐empty subsets of \(\{a_1,a_2,\dots,a_n\}\)). It can be proved that \((2^n-1)\times S\) is an integer. To avoid precision issues, output the value of \((2^n-1)\times S \bmod 998244353\).
inputFormat
The first line contains two integers \(n\) and \(p\) \((1\le n\le 15,\; 2\le p\le 10^9)\) — the number of numbers on the blackboard and the modulus.
The second line contains \(n\) distinct positive integers \(a_1, a_2, \cdots, a_n\) (each less than \(p\)).
(Note: The constraint on \(n\) is small so that an optimal decision tree can be computed via bitmask dynamic programming.)
outputFormat
Output one integer: \((2^n-1)\times S \bmod 998244353\), where \(S\) is the minimum expected number of queries needed in the game.
sample
4 7
1 3 4 630