HDU_4248_A Famous Stone Collector(数学+DPの組み合わせ)

題型:数論
タイトル:
N山の石があって、それぞれの山の色は同じで、任意の2山の色は違います.
すべての石が何種類の異なる配列に並ぶことができるかを聞く.
分析:
挿空法を採用する思想:
dp(i,j)は,前i堆石で長さjのシーケンスに並べられたことを示す.
dp(i,j)という状態については、2つの状態から押し出される.
(1)第iの石を置かず、直接前i-1の石から長さjのシーケンス、すなわちdp(i-1,j)を構成する.
(2)第iの石の中からx個を取り出してシーケンスに入れる長さjのシーケンス,すなわちdp(i−1,j−x)*C(j,x)を構成する.C(j,x)は、j個の位置からx個の位置を選択する組合せ数である.
だから状態遷移方程式:
                                       dp(i,j) = dp(i-1,j) + ∑(dp(i-1,j-x)*C(j,x))
コード:

#include
#include
#include
#include
#define LL long long
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;

const LL mod = 1e9+7;
const int MAXN = 12345;

int n;
LL dp[123][MAXN];
LL c[MAXN][123];
int a[123];

void cal() {
	int x = 10000;
	int y = 100;
	mt(c,0);
	int i,j;
	for(i=0; i<=y; i++)c[0][i]=c[1][i]=1;
	for(i=0; i<=y; i++)c[i][i]=1;
	for(i=0; i<=x; i++)c[i][0]=1;
	for(i=1; i<=x; i++)
		for(j=1; j<=y; j++)
			if(i!=j)
				c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

void DP(){
	mt(dp,0);
	for(int i=1;i<=n;i++){
		dp[i][0] = 1;
	}
	for(int i=1;i<=a[1];i++){
		dp[1][i] = 1;
	}
	int sum = a[1];
	for(int i=2;i<=n;i++){
		sum += a[i];
		for(int j=1;j<=sum;j++){
			int minn = min(j,a[i]);
			dp[i][j] = dp[i-1][j];
			for(int k=1;k<=minn;k++){
				dp[i][j] += dp[i-1][j-k]*c[j][k];
				dp[i][j] %= mod;
			}
		}
	}
}

int main(){
	int _ = 0;

	cal();
	while(~scanf("%d",&n)){
		int sum = 0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			sum += a[i];
		}

		DP();

		LL ans = 0;
		for(int i=1;i<=sum;i++){
			ans += dp[n][i];
			ans %= mod;
		}

		printf("Case %d: %lld
",++_,ans);
	}



	return 0;
}