No.473 和と積の和
タグ : / 解いたユーザー数 53
作問者 :
ctyl_0
/ テスター :
🍡yurahuna
問題文
$N(\geq2)$個の正整数からなる集合$S$を考えます。
$S$から2つの整数$a,b\in S$を選んで取り除き、代わりに$a+b+ab$を集合$S$に加えるという操作を、$S$の要素数が1になるまで繰り返します。
このとき、最後に残った$S$の要素が$X$となることがある集合$S$の個数$M$を答えて下さい。
訂正(2016/12/23 0:15)：この問題文でいう集合とは、数の重複を許しても良い多重集合(multiset)のことです。申し訳ありません。
入力
N X
$N,X$は以下の条件を満たす正整数です。
$2\leq N \leq 100$
$1\leq X \leq 10^9$
出力
M
$S$の要素の並べ替えでつくられる集合は元の集合と同じとみなします。例えば、$S=\{2,2,3\}$と$S=\{3,2,2\}$は集合として等しいので、1通りとみなします。
最後に改行してください。
出力される個数$M$は、$0\leq M \leq 2 \times 10^5$を満たすことが保証されています。
Writer解では、C++14(70ms), Python3(1900ms), PyPy3(630ms)で正解しています。
サンプル
サンプル1
入力
2 15
出力
2
条件を満たす$S$は、$\{1,7\}, \{3,3\}$の$2$通りです。
$S=\{1,7\}$の場合は、$1,7$を選ぶと$1+7+1\times 7=15$となり、$15$を作ることができます。
$S=\{3,3\}$の場合も、$3,3$を選ぶと$3+3+3\times 3=15$となり、$15$を作ることができます。
サンプル2
入力
3 26
出力
1
条件を満たす$S$は、$\{2,2,2\}$の$1$通りです。
1回目の操作で$2,2$を$S$から取り除き、$2+2+2\times 2=8$を$S$に入れます。このとき、$S=\{2,8\}$となっています。
2回目の操作で$2,8$を$S$から取り除き、$2+8+2\times 8=26$となり、条件を満たします。
サンプル3
入力
2 4
出力
0
条件を満たす集合$S$は存在しないことがあります。
サンプル4
入力
6 147026879
出力
147520
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。