[AGC002-F][DP]Leftmost Ball

Description

题解

显然可以先变为颜色第一个球是1~n有序的…最后乘一个颜色数的排列
那我们目标是要满足任意前缀白色球数量>=颜色数量
设一个$dp[i][j]$表示已经放好了$i$个白色球和$j$种颜色
枚举$i,j$，转移可以知道
如果放白色球的话，那么加上$dp[i?1][j]$
否则，我们在这个位置放颜色。为了满足有序当前这个位置一定要放一个颜色，剩下的位置就是$n?K?(K?1)?(j?1)?i?1$个，里面选出$K?2$个来放颜色
预处理组合数就可以$NK$了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
const int MAXN=2005;
const LL mod=1e9+7;
int n,K;
LL inv[MAXN*MAXN],pre[MAXN*MAXN];
LL pow_mod(LL a,LL b)
{
    LL ret=1;while(b){
    if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}LL f[MAXN][MAXN];
LL C(int n,int m){
    return pre[n]*inv[m]%mod*inv[n-m]%mod;}
void ad(LL &x,LL y){
    x+=y;if(x>=mod)x-=mod;}
int main()
{
    n=read();K=read();if(K==1)return puts("1"),0;pre[0]=1;for(int i=1;i<MAXN*MAXN;i++)pre[i]=pre[i-1]*i%mod;inv[MAXN*MAXN-1]=pow_mod(pre[MAXN*MAXN-1],mod-2);for(int i=MAXN*MAXN-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;f[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++){
    if(i-1>=j)ad(f[i][j],f[i-1][j]);ad(f[i][j],f[i][j-1]*C(n*K-(K-1)*(j-1)-i-1,K-2)%mod);}f[n][n]=f[n][n]*pre[n]%mod;pr2(f[n][n]);return 0;
}