传送门: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个人，那么可以直接插空法:
总答案为：
京公网安备 11010502036488号