[0] 準備

• 紙幣の入れ方は、各紙幣を入れる枚数で決まります。そこで、入れ方を長さ \(N\) の非負整数列で表します。 入れ方 \((C_1, C_2, \ldots, C_N)\) と言ったら、各 \(A_i\) 円札を \(C_i\) 枚入れる方法のことを指します。

• 本問題の \(A_i\) たちに関する制約は、位取り記数法のように捉えることができます。特に、非負整数 \(x\) に対して、次の条件を満たす入れ方 \(C = (C_1, C_2, \ldots, C_N)\) が一意に存在することが証明できます。この入れ方を \(x\) 円の貪欲な入れ方ということにします。

  • 合計金額が \(x\) 円。すなわち、\(\displaystyle \sum_{i = 1}^N A_i C_i = x\)
  • \(0 \leq C_i < \dfrac{A_{i+1}}{A_i} \: (1 \leq i \leq N - 1)\)

---

[1] 良い金額の条件

良い金額に関して、次の事実が成り立ちます。

• \(x\) 円が良い金額 \(\iff\) \(x\) 円の貪欲な入れ方において、奇数枚入れる紙幣が存在する

これを証明します。

\((\Longrightarrow) \quad\)対偶を示します。\(x\) 円のどんな入れ方についても、紙幣を可能な限り「両替」していくと、\(x\) 円の貪欲な入れ方になります。\(x\) 円の貪欲な入れ方において、すべての紙幣が偶数枚なので、\(x/2\) 円ずつに分けることが可能です。分けた後、「両替」した紙幣を元に戻すと、元の入れ方も \(x/2\) 円ずつに分かれています。よって、\(x\) 円の良い入れ方は存在せず、\(x\) 円は良い金額ではありません。

\((\Longleftarrow) \quad\) \(x\) 円の貪欲な入れ方において奇数枚の紙幣が存在するとき、それが \(x\) 円の良い入れ方になっていることを示します。すなわち、\(x\) 円の貪欲な入れ方が \(x\) 円の良い入れ方でないとき、その入れ方においてすべての紙幣が偶数枚であることを示します。

\(x\) 円の貪欲な入れ方 \(C = (C_1, C_2, \ldots, C_N)\) が、\(x\) 円の良い入れ方ではないとします。すなわち、次の条件を満たす非負整数列 \(D = (D_1, D_2, \ldots, D_N)\) が存在するとします。

• \(\displaystyle \sum_{i = 1}^N A_i D_i = \frac{x}{2}\)
• \(0 \leq D_i \leq C_i \: (1 \leq i \leq N)\)

このとき、\(C - D = (C_1 - D_1, C_2 - D_2, \ldots, C_N - D_N)\) についても次が成り立ちます。

• \(\displaystyle \sum_{i = 1}^N A_i (C_i - D_i) = \frac{x}{2}\)
• \(0 \leq C_i - D_i \leq C_i \: (1 \leq i \leq N)\)

\(C_ i < \dfrac{A_{i+1}}{A_i} \: (1 \leq i \leq N-1)\) に注意すると、\(D\) および \(C - D\) は \(x/2\) 円の貪欲な入れ方になっていることがわかります。\(x/2\) 円の貪欲な入れ方は一意でしたから、\(D = C - D\) です。すなわち \(C_i = 2D_i \: (1 \leq i \leq N)\) となって、\(C\) のすべての紙幣が偶数枚であることがわかります。

---

[2] 良い金額の数え上げ

以下、「\(M\) 円未満の良い金額ではない金額の個数」を数えることとします（元の問題への変換は容易です）。すなわち、次の条件を満たす \(C = (C_1, C_2, \ldots, C_N)\) の個数を求めます。

• \(\displaystyle \sum_{i = 1}^N A_i C_i < M\)
• \(0 \leq C_i < \dfrac{A_{i+1}}{A_i} \: (1 \leq i \leq N - 1)\)
• \(C_i\) は偶数 \((1 \leq i \leq N)\)

まず、\(M\) 円の貪欲な入れ方を求めておきます。これを \(X = (X_1, X_2, \ldots, X_N)\) とします。

条件を満たす入れ方 \(C\) について、\(C_i < X_i\) を満たす \(1 \leq i \leq N\) が必ず存在します。このうち最大のものを \(j\) とします。直観的には、\(j\) は「初めて下回る桁」です。すると、\(C\) が満たすべき条件は次のようになります。

• \(C_i = X_i \: (j < i \leq N)\)
• \(0 \leq C_j < X_j\)
• \(0 \leq C_i < \dfrac{A_{i+1}}{A_i} \: (1 \leq i < j)\)
• \(C_i\) は偶数 \((1 \leq i \leq N)\)

これを満たす \(C\) の個数は

• \(X_{j+1}, \ldots, X_N\) の中に奇数がある場合、\(0\)
• そうでない場合、\(\displaystyle \left\lceil \frac{X_j}{2} \right\rceil \cdot \prod_{i=1}^{j-1} \left\lceil \frac{A_{i+1} / A_i}{2} \right\rceil\)

となります。\(j\) を全探索して、各 \(j\) について \(O(N)\) 時間で求めても、全体 \(O(N^2)\) 時間となり十分高速です。適切に前計算や差分更新等をすれば、全体 \(O(N)\) 時間にすることも容易です。

また、（本質的にはあまり変わりませんが）桁 DP のような考え方で求めることもできます（詳細は割愛します）。