No.473 Sum of Sum and Product
Problem Statement
Consider a set $S$ consisting of $N(\geq2)$ positive integers.
Repeat the following operation until the number of elements of $S$ becomes 1: choose two integers $a,b\in S$ from $S$, remove them, and add $a+b+ab$ to the set $S$ instead.
Find the number $M$ of sets $S$ for which the last remaining element of $S$ can be $X$.
Correction (2016/12/23 0:15): The term "set" in this problem statement means a multiset, in which duplicate numbers are allowed. We apologize for the error.
Input
N X
$N,X$ are positive integers satisfying the following conditions.
$2\leq N \leq 100$
$1\leq X \leq 10^9$
Output
M
Sets obtained by rearranging the elements of $S$ are considered the same as the original set. For example, $S=\{2,2,3\}$ and $S=\{3,2,2\}$ are equal as sets, so they are counted as one.
Print a newline at the end.
It is guaranteed that the output count $M$ satisfies $0\leq M \leq 2 \times 10^5$.
The writer's solutions were accepted in C++14 (70ms), Python3 (1900ms), and PyPy3 (630ms).
Sample
Sample 1
Input
2 15
Output
2
The sets $S$ satisfying the condition are the following $2$: $\{1,7\}, \{3,3\}$.
For $S=\{1,7\}$, choosing $1,7$ gives $1+7+1\times 7=15$, so $15$ can be made.
For $S=\{3,3\}$ as well, choosing $3,3$ gives $3+3+3\times 3=15$, so $15$ can be made.
Sample 2
Input
3 26
Output
1
The only set $S$ satisfying the condition is the following $1$: $\{2,2,2\}$.
In the first operation, remove $2,2$ from $S$ and put $2+2+2\times 2=8$ into $S$. At this point, $S=\{2,8\}$.
In the second operation, remove $2,8$ from $S$, which gives $2+8+2\times 8=26$, satisfying the condition.
Sample 3
Input
2 4
Output
0
There may be no set $S$ satisfying the condition.
Sample 4
Input
6 147026879
Output
147520
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
🍡yurahuna