ABC156:E-简单组合数学

传送门:https://atcoder.jp/contests/abc156/tasks/abc156_e

题目大意：给你n个房间，每个房间里一个人。一次移动可以使得一个人移动到除本身外的任意一个房间里去。问k次移动之后，房间有多少种组合状态。

例如： n = 3 , k = 2.

状态有:(0,0,3),(0,3,0),(3,0,0),(0,1,2),(0,2,1),(1,2,0),(2,1,0),(1,1,1),(1,0,2),(2,0,1).

题目思路：

,任何局面可以达成，就是求不定方程非负整数解的个数.我们可以用一一映射+插空法。答案为：

.等价于：

当时我推到这里就卡住了。想用dp做，但是只能想出的.

因为我这里漏掉了一个很重要的条件: 未知数的个数 = 所求的数.

那么就意味着，当存在着一个数 >= k 时，那么必将至少有 k - 1 个空格产生.

所以上述条件可以转换为:局面中存在有个空房间。

那么我们可以用总的减去不合法的，当然也可以直接算。

空房间的组合情况为：

剩下来的房间最少都有1个人，那么可以直接插空法:

总答案为：