【agc002f】Leftmost Ball（動態規劃）
題面
atcoder
洛谷
題解
我們從前往后依次把每個顏色按順序來放，那么如果當前放的是某種顏色的第一個球，那么放的就會變成\(0\)號顏色，所以無論何時，\(0\)號顏色的數量不能少于其他顏色的數量。
可以設狀態\(f[i][j]\)表示前面一共放了\(i\)個\(0\)號顏色的球，而一共出現了\(j\)種其他顏色的球，根據上面的東西，可以知道\(i\ge j\)。每次轉移我們分成兩種考慮。第一種就直接在后面接一個\(0\)號顏色的球，這個不需要考慮任何決策，直接轉移即可，也就是\(f[i][j]+=f[i-1][j]\)。另外一種轉移是選擇一共新的顏色，拋去前面已經放好的\(0\)號顏色的前，拋去當前位置放下一個當前顏色的球，那么還需要在后面選擇\(k-2\)個位置來放這些球，而后面剩下的空位個數顯然是可以算的。首先還剩下\(n-i\)個\(0\)號顏色的球沒有放，所以提供\(n-i\)個空位，前面一共只出現了\(j-1\)種顏色，所以還有\((n-j+1)*(k-1)\)個空位，但是當前的位置被欽定放這種新的顏色，所以還要減少一個位置。
也就是轉移長成這個樣子：
\[f[i][j]=f[i-1][j]+C_{(n-i)+(n-j+1)*(k-1)-1}^{k-2}*f[i][j-1]*(n-j+1)\]
時間復雜度\(O(nk)\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 2010
#define MOD 1000000007
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,k,mx,f[MAX][MAX];
int jc[MAX*MAX],jv[MAX*MAX],inv[MAX*MAX];
int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int main()
{n=read();k=read();mx=n*k;if(k==1){puts("1");return 0;}jc[0]=jv[0]=inv[0]=inv[1]=1;for(int i=1;i<=mx;++i)jc[i]=1ll*jc[i-1]*i%MOD;for(int i=2;i<=mx;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;for(int i=1;i<=mx;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;f[0][0]=1;for(int i=1;i<=n;++i)for(int j=0;j<=i;++j){add(f[i][j],f[i-1][j]);if(j)add(f[i][j],1ll*f[i][j-1]*(n-j+1)%MOD*C((n-i)+(n-j+1)*(k-1)-1,k-2)%MOD);}printf("%d\n",f[n][n]);return 0;
}
)
