SRM Div2 hard : VocaloidsAndSongs

問題概要：
S個の歌がある
その音楽を３人のボーカロイドGumi, Ia, Mayuが歌う
Gumi は gumi回、 Ia は ia回、 Mayu は mayu回だけ歌う
S個の歌は少なくとも３人のうち1人に歌われなければならない
そのような歌に対するボーカロイドの割り当て方は何通り存在するか
答えは大きくなるので1000000007でmodをとること

解法：
以下の図について考える

aはGumiだけが歌う曲の数
bはIaだけが歌う曲の数
cはMayuだけが歌う曲の数
dはGumiとIaだけが歌う曲の数
eはGumiとMayuだけが歌う曲の数
fはMayuとIaだけが歌う曲の数
gはGumiとIaとMayuの３人が歌う曲の数

ここでd,e,f,gをループで決めてしまう(最大50*50*50*50)
これさえ決まればSをつかってa,b,cは復元できる
答えはそれら全てのd,e,f,gに対する組み合わせとなるので、
C[S][a] * C[S-a][b] * C[S-a-b][c] * C[S-a-b-c][d] * C[S-a-b-c-d][e] * C[S-a-b-c-d-e][f] * C[S-a-b-c-d-e-f][g]の総和となる
C[a][b]はコンビネーション aCb
掛け算の際にオーバーフローしないように注意すること

コード：

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;

ll C[MAX][MAX];
 
class VocaloidsAndSongs {
public:

  ll modmultiply(ll a,ll b) {
    ll c = MOD;
    ll x = 0,y = a%c; 
    while(b > 0) {
      if(b%2 == 1) {
	x = (x+y)%c;  }
      y = (y*2)%c;
      b /= 2; }
    return x%c;  
  }

  void makeC()
  {
    C[0][0] = 1;
    rep(i,MAX-1)rep(j,i+1)
      {
	C[i+1][j] += C[i][j]%MOD;
	C[i+1][j] %= MOD;
	if(j+1<MAX){
	  C[i+1][j+1] += C[i][j]%MOD;
	  C[i+1][j+1] %= MOD;
	}
      }
  }

  int count( int S, int gumi, int ia, int mayu ) {
    makeC();

    ll ans = 0;
    rep(d,S+1){
      rep(e,S+1){
	if(d+e > S)break;
	rep(f,S+1){
	  if(d+e+f > S)break;
	  rep(g,S+1){
	    if(d+e+f+g > S)break;
	    int a = gumi - (d+g+e);
	    if(a < 0)continue;
	    int b = ia - (d+g+f);
	    if(b < 0)continue;
	    int c = mayu - (e+g+f);
	    if(c < 0)continue;

	    if(a+b+c+d+e+f+g != S)continue;
	    if( a < 0 || b < 0 || c < 0 || d < 0 || e < 0 || f < 0 || g < 0)continue;

	    ll value = 1;
	    value = modmultiply(value,C[S][a]);
	    value = modmultiply(value,C[S-a][b]);
	    value = modmultiply(value,C[S-a-b][c]);
	    value = modmultiply(value,C[S-a-b-c][d]);
	    value = modmultiply(value,C[S-a-b-c-d][e]);
	    value = modmultiply(value,C[S-a-b-c-d-e][f]);
	    value = modmultiply(value,C[S-a-b-c-d-e-f][g]);
	    ans = ( ans + value ) % MOD;
	  }
	}
      }
    }
    return ans%MOD;
  }

};