Let \((c_1, \dots, c_n)\) (call it Snuke’s hand) denote the fact that Snuke has \(c_j\) copies of Card \(j\).

The necessary and sufficient condition for being Snuke’s possible hand

When you can exchange cards, you may always do so

Let us consider a function \(f(c_1,\dots,c_n) = \sum_{j=1}^n 2^{j-1}(j-1)!c_j\) that answers the following question: “initially we had just copies of Card \(1\), then exchanged cards some number of times, and now our hand is \((c_1,\dots, c_n)\). What is the minimum possible number of copies of Card \(1\) we initially had?” The remainder when the value of this function is divided by \(N := 2^nn! - 1\) does not change by exchanging cards. From this, we can show that when to exchange cards is irrelevant to what the final hand will be, so we will always do so when possible. Then, we only need to consider hands \((c_1,\dots, c_n)\) such that \(0 \le c_j \lt 2j\).

The necessary and sufficient condition

This function takes the same value modulo \(N\) only when \(f(0,\dots,0)\equiv f(2 - 1,\dots,2n-1)\equiv 0 ~(\text{mod } N)\), but the constraints guarantee that our hand cannot be empty, so we can assume that there is one-to-one correspondence between the hands and the values of the function.

The necessary and sufficient condition for \((d_1,\dots,d_n)\neq (0,\dots,0)\) being Snuke’s possible hand is \begin{aligned} d \equiv c ~(\text{mod gcd} (N,s_1,\dots,s_m)) ~\cdots (1) \end{aligned} where \(c=f(c_1,\dots,c_n) \text{ mod } N,d=f(d_1,\dots,d_n) \text{ mod } N, s_i=f(s_{i,1},\dots,s_{i,n})\text{ mod } N\).

Proof

It follows from the Chinese remainder theorem (or extended Euclidean algorithm) that (1) is equivalent to (1’):

\begin{aligned} \exists a_0\dots,a_m\in \mathbb{Z}, d - c = a_0N+a_1s_1+\dots +a_ms_m ~\cdots (1’) \end{aligned}

Let \(a_1,\dots,a_m\) be the numbers of times we buy Card Pack \(i\), and \(-a_0\) be the number of times we exchange cards with \(j=n\). Then, we have \(d = c + a_0N+a_1s_1+\dots +a_ms_m\), so (2) is a necessary and sufficient condition for \((d_1,\dots,d_n)\) being a possible hand.

Thus, we just need to show that (1’) and (2) are equivalent. It is obvious that (1’) holds if (2) holds, so we will show (2) from (1). Let us take integers \(a_0,\dots,a_m\) such that \(d - c = a_0N+a_1s_1+\dots +a_ms_m\). For \(j=1,\dots,m\) in this order, do the following operation:

while (a_0 > 0 or a_j < 0) {
    a_0 -= s_j // decreases a_0 N + a_1 s_1 + ... + a_m s_m  by N s_j 
    a_j += N // increases a_0 N + a_1 s_1 + ... + a_m s_m by N s_j
}

Then, \(a_0,\dots,a_m\) will satisfy all conditions in (2).

Solution

Let \(g:=\text{gcd} (N,s_1,\dots,s_m)\).

When \(g\) is large

There are only \(N/g\) possible hands not greater than \(N\). If we can afford \(O(N/g)\) time, try them all.

When \(g\) is small

Consider it as the shortest path problem and do a breadth-first search to solve it in \(O(gn)\) time.

More specifically, consider a graph with vertices \(0,\dots,g-1\) corresponding to the hand \((d_1,\dots,d_n)\) being \(f(d_1,\dots,d_n) \text{ mod } g =0,1,\dots,g-1\) and directed edges \((v+1) \text{ mod } g,\dots,(v+2^{j-1}(j-1)!) \text{ mod } g,\dots,(v+2^{n-1}(n-1)!) \text{ mod } g\). The answer is the length of the shortest path from the vertex \(0\) to the vertex \(f(c_1,\dots,c_n) \text{ mod } g\) (considering only paths of length greater than \(0\)).

Solution for the general case

There are only \(15\) possible values for \(N\): \(2^22! - 1,2^33! - 1\dots,2^{16}16! - 1\), and the gcd can only be a divisor of one of them. After writing a program to list their divisors or using WolframAlpha, it turns out that each of those divisors is large or small, which enables us to solve the problem.

Sample Implementation in C++

Sample Implementation in Python