盒子与球

ID: 285

远端评测题

1000ms

125MiB

难度: 2

上传者:

标签>

数学

题目描述

现有 $r$ 个互不相同的盒子和 $n$ 个互不相同的球，要将这 $n$ 个球放入 $r$ 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

输入只有一行两个整数，分别代表 $n$ 和 $r$ 。

输出一行一个整数代表答案。

3 2

有两个盒子（编号为 $1, 2$ ）和三个球（编号为 $1, 2, 3$ ），共有六种方案，分别如下：

盒子编号	方案 1	方案 2	方案 3	方案 4	方案 5	方案 6
盒子 $1$	小球 $1$	小球 $2$	小球 $3$	小球 $2, 3$	小球 $1, 3$	小球 $1, 2$
盒子 $2$	小球 $2, 3$	小球 $1, 3$	小球 $1, 2$	小球 $1$	小球 $2$	小球 $3$

对于 $100\%$ 的数据，保证 $0 \leq r \leq n \leq 10$ ，且答案小于 $2^{31}$ 。