TC VocaloidsAndSongs

VocaloidsAndSongs

Problem Statement    Problem Statement for VocaloidsAndSongs Problem Statement      Vocaloids Gumi, Ia, and Mayu love singing. They decided to make an album composed of S songs. Each of the S songs must be sung by at least one of the three Vocaloids. It is allowed for some songs to be sung by any two, or even all three Vocaloids at the same time. The number of songs sang by Gumi, Ia, and Mayu must be gumi, ia, and mayu, respectively.  They soon realized that there are many ways of making the album. Two albums are considered different if there is a song that is sung by a different set of Vocaloids. Let X be the number of possible albums. Since the number X can be quite large, compute and return the number (X modulo 1,000,000,007).   Definition      Class: VocaloidsAndSongs Method: count Parameters: int, int, int, int Returns: int Method signature: int count(int S, int gumi, int ia, int mayu) (be sure your method is public)        Constraints - S will be between 1 and 50, inclusive. - gumi, ia and mayu will be each between 1 and S, inclusive.   Examples 0)      3 1 1 1 Returns: 6 In this case, there are 3 songs on the album. And Gumi, Ia, Mayu will each sing one song. There are 3*2*1 = 6 ways how to choose which Vocaloid sings which song. 1)      3 3 1 1 Returns: 9 Gumi will sing all three songs. Ia and Mayu can each choose which one song they want to sing. 2)      50 10 10 10 Returns: 0 It is not possible to record 50 songs if each Vocaloid can only sing 10 of them. 3)      18 12 8 9 Returns: 81451692 4)      50 25 25 25 Returns: 198591037 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:         Single Round Match 609 Round 1 - Division II, Level Three

-------------------------------------------------editorial--------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli dp[51][51][51][51];
#define mod 1000000007
int solve(int s,int g,int ia,int m)
 {
 
    if(g<0 || ia<0 || m<0) return 0;
    if(s==0  && g==0 && ia==0 && m==0) return 1;
    else if(s==0) return 0;
 
   else if(dp[s][g][ia][m]!=-1) return dp[s][g][ia][m];
   else
   {
    lli ret=0;
    ret=solve(s-1,g-1,ia,m);
    ret=(ret+solve(s-1,g,ia-1,m))%mod;
    ret=(ret+solve(s-1,g,ia,m-1))%mod;
   
    ret=(ret+solve(s-1,g-1,ia-1,m))%mod;
    ret=(ret+solve(s-1,g,ia-1,m-1))%mod;
    ret=(ret+solve(s-1,g-1,ia,m-1))%mod;
    ret=(ret+solve(s-1,g-1,ia-1,m-1))%mod;
   
    dp[s][g][ia][m]=ret;
    return ret;
  }
 }
int count(int s, int gumi, int ia, int mayu)
{
 memset(dp,-1,sizeof dp);
   int ans=solve(s,gumi,ia,mayu);
   return ans;
}
int main()
 {
  int s,a,b,c;
  cin>>s>>a>>b>>c;
  cout<<count(s,a,b,c)<<endl;
 }