カード \(j\) を持っている枚数が \(c_j\) 枚であるとき \((c_1,\dots, c_n)\) と書き、これを手札と呼ぶことにします。

すぬけくんの手札としてありうる必要十分条件

カードは交換できるとき常に交換して問題ない

「カード \(1\) だけを持っている状態から交換を繰り返して手札が \((c_1,\dots, c_n)\) になったとき、最初に持っていたカード \(1\) の何枚は最小で何枚か？」を表す関数 \( f(c_1,\dots,c_n) = \sum_{j=1}^n 2^{j-1}(j-1)!c_j\) を考えます。 この関数の値を \(N := 2^nn! - 1\) で割ったあまりはカードの交換の前後で変わりません。 このことから、カードを交換するタイミングは最終的な手札に影響を与えないことが示せるため、カードが交換できるときは常に交換することにします。 このとき、手札 \((c_1,\dots, c_n)\) として \(0\le c_j \lt 2j\) を満たすもののみを考えれば十分です。

必要十分条件

この関数が \(N\) を法として同じ値を取る場合は \(f(0,\dots,0)\equiv f(2 - 1,\dots,2n-1)\equiv 0 ~(\text{mod } N)\) のみですが、入力の制約から手札が \(1\) 枚もなくなることはありえないため、手札と関数の値は一対一対応するとみなして良いです。

\((d_1,\dots,d_n)\neq (0,\dots,0)\) がすぬけくんの手札としてありうる必要十分条件は、 \(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\) とすると、次のように書けます。

\[\begin{aligned} d \equiv c ~(\text{mod gcd} (N,s_1,\dots,s_m)) ~\cdots (1) \end{aligned}\]

証明

中国剰余定理（拡張ユークリッド互除法）から、(1) と (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}\]

また、\(a_1,\dots,a_m\) をカードパック \(i\) を買う回数とし、\(-a_0\) を \(j=n\) を選んでカードを交換する回数とすると、 \(d = c + a_0N+a_1s_1+\dots +a_ms_m\) であるため、(2) は手札として \((d_1,\dots,d_n)\) がありうることの必要十分条件です。

\[\begin{aligned} \exists a_0\dots,a_m\in \mathbb{Z}, a_0\le 0 \land a_1,\dots, a_m\ge 0 \land d - c = a_0N+a_1s_1+\dots +a_ms_m ~\cdots (2) \end{aligned}\]

よって (1’) と (2) が同値であることを示せば良いです。(2) ならば (1’) は自明なので、(1’) から (2) を示します。 \(d - c = a_0N+a_1s_1+\dots +a_ms_m\) を満たす 整数 \(a_0,\dots,a_m\) を取ります。 \(j=1,\dots,m\) について順番に、次の操作をします。

while (a_0 > 0 or a_j < 0) {
    a_0 -= s_j // a_0 N + a_1 s_1 + ... + a_m s_m  が N s_j 減る 
    a_j += N // a_0 N + a_1 s_1 + ... + a_m s_m が N s_j 増える
}

すると、(2) の条件をすべて満たす \(a_0,\dots,a_m\) が得られます。

解法

\(g:=\text{gcd} (N,s_1,\dots,s_m)\) とおきます。

\(g\) が大きいときの解法

\(N\) 以下の候補は \(N/g\) 個しか無いため、\(O(N/g)\) が間に合う場合、全部試せば良いです。

\(g\) が小さいときの解法

最短経路問題とみなして幅優先探索をすれば \(O(gn)\) で解けます。

具体的には、手札 \((d_1,\dots,d_n)\) が \(f(d_1,\dots,d_n) \text{ mod } g =0,1,\dots,g-1\) である場合それぞれに頂点 \(0,\dots,g-1\) を対応させて、頂点 \(v\) から \((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\) に有向辺を張ったグラフを考えます。 このグラフ上の頂点 \(0\) から頂点 \(f(c_1,\dots,c_n) \text{ mod } g\) への（長さ \(1\) 以上の経路を考えた場合の）最短経路長が答えです。

一般の解法

\(N\) としてありうる値は\(2^22! - 1,2^33! - 1\dots,2^{16}16! - 1\) の \(15\) 通りなので、gcd としてありうる値もこれらの約数しかありません。 プログラムを書いて約数を列挙してみたり WolframAlpha を使うなどと行った方法でこれらの約数について調べてみると、実はどの約数も大きいか小さいかのどちらかであることが分かります。 よって、この問題を解くことができました。

C++による実装例

Pythonによる実装例