BZOJ4665: 작은 w의 결혼 사탕[dp, 용기

...QwQ가 만든 첫 번째 이런 문제
f[i][j]는 전 i종을 분배한 것을 나타낸다. 적어도 j 개인이 합법적이지 않다는 것을 의미한다. 그리고 한 번 질책하면 된다.
마지막으로 통계를 낼 때 남은 n-j 개인의 분배 방법은(n-j)!각 설탕의 잉여 수량의 곱셈을 나누면, 이 곱셈은 직접 dp에 있을 때 계산된다

#include
#define MOD 1000000009
#define MAXN 2005
using namespace std;	int n;
int x[MAXN];
int C[MAXN][MAXN];
int jc[MAXN],_jc[MAXN];

int f[MAXN][MAXN];

inline int POW(long long d,long long c){
	long long rtn=1;
	for(;c;c>>=1,d=d*d%MOD)
		if(c&1)	rtn=rtn*d%MOD;
	return (int)rtn;
}

inline void Plus(int &a,const int b){
	a+=b;
	if(a<0)	a+=MOD;
	if(a>=MOD)	a-=MOD;
}

inline void init(){
	C[0][0]=1;
	for(register int i=1,j;i<=n;++i)
		for(j=1,C[i][0]=1;j<=i;++j)
			C[i][j]=C[i-1][j-1],Plus(C[i][j],C[i-1][j]);
	jc[0]=1;
	for(register int i=1;i<=n;++i)	jc[i]=1ll*jc[i-1]*i%MOD;
	_jc[n]=POW(jc[n],MOD-2);
	for(register int i=n-1;~i;--i)	_jc[i]=1ll*_jc[i+1]*(i+1)%MOD;
}

int read_x;
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d",&n);
	
	init();
	for(int i=1;i<=n;++i)	scanf("%d",&read_x),++x[read_x];
	int tot=0;
	f[0][0]=1;
	for(int i=1;i<=n;tot+=x[i++])
		for(int j=0;j<=tot;++j)
			for(int k=0;k<=x[i];++k)
				Plus(f[i][j+k],1ll*f[i-1][j]*C[x[i]][k]%MOD*_jc[x[i]-k]%MOD);//,printf("f[ %d ][ %d ] = %d
",i,j+k,f[i][j+k]);
	int ans=0;
//	for(int i=0;i<=tot;++i)	printf("%d
",f[n][i]);
	for(int i=0;i<=tot;++i)
		Plus(ans,(i&1?-1ll:1ll)*f[n][i]*jc[tot-i]%MOD);
	printf("%d",ans);
	return 0;
}