問題一覧 > 通常問題

No.473 Sum of Sum and Product

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : ctyl_0 / テスター : 🍡yurahuna
お気に入りにしたユーザー ProblemId : 1437 / 自分の提出
問題文最終更新日: 2026-06-25 02:49:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。