TopCoder Open '09 Round5 Medium LineOfDice

解説読んでもなかなか理解できなかった。

問題

一番上の面が1,2,3,4,5,6であるようなサイコロの数がそれぞれ与えられる。
サイコロは、一番上の面を変えないようにして自由に回転することができる。


サイコロを、隣り合う面が同じであるようにして一列に並べる。
(使わないサイコロがあってもよい)
サイコロを並べる並べ方の場合の数を求めよ。
ただし、並び方は並んでいるサイコロの面が一つでも異なるとき異なるとみなすことにする。

制約条件

それぞれのサイコロの数≦1000

方針

サイコロの列は、左端のサイコロの左側の面を決めると、
全部のサイコロの左側の面が決まる。


例えば、左端のサイコロの左の面を2にすると、全部のサイコロの左の面は5,2,5,2,...
そして、左の面を2または5にするように置けるのは、上または下の面が2でないようなサイコロ。


よって左側の面を一つに決めると次のようなdpができる。
dp[i][j]をサイコロをi種類使って長さjの列を作る場合の数とすると、
dp[i][j]=dp[i-1][j-x]*C[j][x] (0≦x≦(i番目のサイコロの数))の式が成り立つ。

ソースコード

const int mod=10007;
int C[6010][1010], dp[5][6010];

class LineOfDice {
	public:
	int howMany(vector <int> dice) 
	{
		rep(i,6001)rep(j,min(i+1,1001)){
			C[i][j]=i==0||j==i?1:(C[i-1][j-1]+C[i-1][j])%mod;
		}
		
		int ans=0;
		
		rep(left,6){
			int d[4],nd=0;
			rep(i,6)if(i!=left&&i!=5-left)d[nd++]=dice[i];
			rep(i,5)rep(j,6001)dp[i][j]=0;
			dp[0][0]=1;
			
			rep(i,4){
				rep(j,6001)rep(x,min(j,d[i])+1){
					(dp[i+1][j]+=dp[i][j-x]*C[j][x])%=mod;
				}
			}
			rep(i,6000)(ans+=dp[4][i+1])%=mod;
		}
		return ans;
	}
};