TopCoder SRM 609 Div2 Hard VocaloidsAndSongs

Div2 Hardとはいええらい安直な問題。
950ptだからか。
http://community.topcoder.com/stat?c=problem_statement&pm=12989

問題

S個の曲があり、３人でそれらの曲を歌う。
３人が歌える歌の数は決まっており、それを超えても足りなくても行けない。
また、各曲は最低１人以上が歌わなければならない。

S個の曲の歌い方の組み合わせ数を求めよ。

回答

Sが50と小さいので、３人の残り歌える回数を状態としてDPすれば良い。
３人の状態とS個の曲で合わせて計算量はO(S^4)。

ll mo=1000000007;
ll dpdp[2][51][51][51];

class VocaloidsAndSongs {
	public:
	int count(int S, int gumi, int ia, int mayu) {
		int i,x,y,z;
		ZERO(dpdp);
		dpdp[0][gumi][ia][mayu]=1;
		FOR(i,S) {
			int cur=i%2,tar=cur^1;
			ZERO(dpdp[tar]);
			FOR(x,51) FOR(y,51) FOR(z,51) {
				if(dpdp[cur][x][y][z]==0) continue;
				
				if(x&&y&&z) dpdp[tar][x-1][y-1][z-1] = (dpdp[tar][x-1][y-1][z-1] + dpdp[cur][x][y][z]) % mo;
				if(x&&y) dpdp[tar][x-1][y-1][z] = (dpdp[tar][x-1][y-1][z] + dpdp[cur][x][y][z]) % mo;
				if(x&&z) dpdp[tar][x-1][y][z-1] = (dpdp[tar][x-1][y][z-1] + dpdp[cur][x][y][z]) % mo;
				if(y&&z) dpdp[tar][x][y-1][z-1] = (dpdp[tar][x][y-1][z-1] + dpdp[cur][x][y][z]) % mo;
				if(x) dpdp[tar][x-1][y][z] = (dpdp[tar][x-1][y][z] + dpdp[cur][x][y][z]) % mo;
				if(y) dpdp[tar][x][y-1][z] = (dpdp[tar][x][y-1][z] + dpdp[cur][x][y][z]) % mo;
				if(z) dpdp[tar][x][y][z-1] = (dpdp[tar][x][y][z-1] + dpdp[cur][x][y][z]) % mo;
			}
		}
		
		return dpdp[S%2][0][0][0];
	}
};

まとめ

今回のSRMはDiv1 Hard以外はあまりトリッキーな問題がない感じ。