设 f[i][j] 表示（前）i 个球装入 j 个盒子中的方案数

目标：cout<<f[n][m];

单独考虑第 i 个球：

（1）自己占一个盒子： f[i][j]=f[i-1][j-1]×(m-j+1);

（2）自己和其他球共占一个盒子： f[i][j]=f[i-1][j]×(j-k+1);

感谢zt哥哥提供的思路\bx

题目描述

有 n 个小球，编号为 1 ~ n。

有 m 个盒子，编号为 1 ~ m。

Bob 要将这 n 个小球装进 m 个盒子。他要求：

1.每个盒子中至少有一个小球。

2.如果一个盒子中有不止一个小球，则该盒子中任意两个小球的编号的差的绝对值都不能小于 k。

问：Bob 有多少种不同的装球方案？

两种方案被认为不同，当且仅当存在一个小球 i, 在两种方案中放入的盒子的编号不同。

输出方案数模 1,000,000,007 的值。

思路

对于整体分析方案数不太现实，我们考虑每次多放一个球，方案数会有什么变化，显然可以 dp。

设 $dp[i][j]$ 表示前 $i$ 个球（有编号），放进 $j$ 个盒子（无编号）的方案数，边界条件 $dp[0][0]=1$。最终答案 $dp[n][m]\times m!$，乘阶乘是因为盒子有编号。

显然放球顺序对答案没有影响，钦定按编号放球，每次放球都要保证合法。

考虑转移，每次多加一个球，有两种选择：

• 开新盒子放，方案数为 $dp[i-1][j-1]$，也就是钦定第 $j$ 个盒子给第 $i$ 个球
• 所有盒子都有球了，选合法的放，由于前面放了 $i-1$ 个球，我们发现 $[max(i-k,1),i]$ 中的任意两个球不能在同一个盒子里，所以 $[max(i-k,1),i-1]$ 这 $k-1$ 个球各占一个盒子，剩下 $max(j-(k-1),0)$ 个盒子可以放，继承 $dp[i-1][j]$ 的方案数，根据乘法原理，答案为两数相乘。

代码如下

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1010,mod=1e9+7;
int n,m,k; 
int dp[N][N];
signed main(){
	cin >> n >> m >> k;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=(dp[i-1][j-1]+max(0ll,j-k+1)*dp[i-1][j])%mod;
		}
	}
	int t=1;
	for(int i=1;i<=m;i++){
		t=(t*i)%mod;
	}
	int ans=(dp[n][m]*t)%mod;
	cout << ans;
	return 0;
}