计数类组合数DP（玩个球）A3

n种颜色的球，每种m个，给出一个这些球的排列，就会从左往右把第一个遇到的某种颜色涂白。问有多少不一样的颜色序列(n,m<=2000)

发现白色的球都一样，当成一种算，我们只关注当前：（1）白色的球放了几个（2）不是白色的球，在属于它的白色确定了之后是可以随便放的。dp[i][j]:已经放了i个白色ball，放完了j种颜色的方案数，转移考虑当前位置（1）放白色的球=dp[i-1]j有颜色的球，可以从dp[i][j-1]转移，颜色可以选(n-(j-1))个，剩下的n * m-(m-1)*(j-1)-i-1个位置，我都一次性放完这种颜色的球

这种计算方式是不会重复的,你可能会觉得每种转移都用组合数算，那组合套组合不会存在某种重复的计数情况吗？其实不会，因为dp[i[j]本身就可以完全代表我已经选过的球的数量和位置信息，它内部的排列是我以前计算过的我不关心，我只关注剩下的位置的填数情况，也就是剩余位置的排列确定了，就往里面塞就行，一定不重复。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<ctime>
#include<bitset>
using namespace std;
#define  _f(i,a,b) for(register int i=a;i<=b;++i)
#define  f_(i,a,b) for(register int i=a;i>=b;--i)
#define ll long long
#define INF 2147483647
#define chu printf
#define rint register int
inline ll re(){
	ll x=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')h=-1;ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
	}
	return x*h;
}
const int N=4000000+100;
int n,m;
bool vis[2000000];
ll dp[2100][2100];
int fi[5];
int a[N],b[N];
ll mod=1e9+7;
ll ny[N],sny[N],fac[N];
inline void pre()
{
	ny[0]=sny[0]=fac[0]=ny[1]=sny[1]=fac[1]=1;
	_f(i,2,n*m)
	{
		fac[i]=fac[i-1]*i%mod;
		ny[i]=(mod-mod/i)*ny[mod%i]%mod;
		sny[i]=ny[i]*sny[i-1]%mod;
	}
}
inline ll C(int x,int y)
{
	return fac[x]*sny[y]%mod*sny[x-y]%mod;
}
int main()
{
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	n=re(),m=re();
	pre();
	dp[0][0]=1;
	_f(i,1,n)
	{
		dp[i][0]=1;
		_f(j,1,i)//最多i种放完的球
		{
			dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;//放白球
			//chu("(last)dp[%d]%d:%lld\n",i,j,dp[i][j]);
			if(j>0)dp[i][j]=(dp[i][j]+dp[i][j-1]*(n-j+1)%mod*C(n*m-(j-1)*(m-1)-i-1,m-2)%mod)%mod;
			//j-1:上次还只有j-1个放完了，m-1：白球从色球里抛了
			//chu("dp[%d][%d]:%lld\n",i,j,dp[i][j]);
		}
	}
	chu("%lld",dp[n][n]);
	return 0;
}
/*
40分可真不容易（只是个暴力啊......）
进制数计算的时候一定仔细想，10进制9位已经相当大了（还开个2000的数组？）
组合数不能用杨辉三角递推（排列数可以）
dp[i][j]:表示放i个白球，有j个颜色放完的方案数
如果第i+j*(m-1)+1个位置放白球，白球没有区别，我们从dp[i-1][j]转移
如果放颜色球，有n*m-j*(m-1)-i-1个剩余位置，默认当前放的颜色第一次出现，*(n-j+1)*C( ,m-2)
*/