Volleyball Match (number of ways to score a,b)

Volleyball Match 

Tatyana is a big sports fan and she likes volleyball a lot! She writes down the final scores of the game after it has ended in her notebook.

If you are not familiar with the rules of volleyball, here's a brief:

• 2 teams play in total
• During the course of the game, each team gets points, and thus increases its score by 1.
• The initial score is 0 for both teams.

The game ends when

• One of the teams gets 25 points and another team has < 24 points ( strictly less than 24).
• If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.

Given the final score of a game in the format A:*B* i.e., the first team has scored A points and the second has scored B points, can you print the number of different sequences of getting points by teams that leads to this final score?

Input Format 
The first line contains A and the second line contains B.

Constraints

0 ≤ A , B ≤ 109

Output Format 
Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 109+7, output number modulo 109 + 7. Print 0 if no such volleyball game ends with the given score.

Example input #00

3
25

Example output #00

2925

Example input #01

24
17

Example output #01

0

Explanation #01

There's no game of volleyball that ends with a score of 24 : 17.

========================editorial==============================

At first, there are a few tricky cases that should be considered. The answer in each of these cases is 0

• A = 24, B = 25, or vice versa. The game hasn't ended in this case.
• The both A and B are less than 25.
• A = B
• One of the teams's scores is greater than 25 and the difference between the teams' scores is different from 2.

After checking these cases, let's calculate a number of games that has the intermediary score of X : Y over all the possible pairs (X, Y) where the both X and Y are not greater than 25. Let's name it S(X, Y). By intermediary we mean the the game doesn't have to be ended with this score (but this score CAN correspond to some ended game, as well).

We can calculate S(X, Y) using the recurrent formula: S(X, Y) = S(X - 1, Y) + S(X, Y - 1) in the general case, starting with S(0, 0) = 1. As we can see, it's quite similar to the Pascal Triangle, so we can use the number of combinations instead of the recurrent formula. Nevertheless, the writer of the problem considers recurrent formula the simplest solution.

Now, if both A and B aren't greater than 25, we can just output the value of S(A-1, B) or S(A, B-1) (depending on who is the winner of the game) modulo 109 + 7.

What happens if A or B (or both) are greater than 25. That means the the score of 24 : 24 was reached during the game. Then, the score of 25 : 25 was also reached. Otherwise it would mean that the game ends with the score of 24 : 26 or 26 : 24. There are two ways to reach 25 : 25 from 24 : 24. Then, the score of 26 : 26 was also reached, and again there're two ways to go from 25 : 25 to 26 : 26. This goes on, till the score of min(A, B) : min(A, B) is reached. Then, one of teams gains two points in a row and the game ends. There are always two ways to get C : C from C-1 : C-1.

So, according to the simplest combinatorial rules, if max(A, B) is greater than 25, the answer is S(24, 24) * 2min(A, B) - 24.

==============================code=======================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli dp[27][27];

#define mod 1000000007

lli power(lli a,lli b)

{

 

if(b==0) return 1;

if(b==1) return a;

else

{

lli temp=power(a,b/2);

if(b%2==0)

{

return (temp*temp)%mod;

}

else

{

lli ret=(temp*temp)%mod;

ret=(ret*a)%mod;

return ret;

}

}

}

lli solve(int a,int b)

{

//cout<<a<<" "<<b<<endl;

 //cout<<dp[a][b]<<endl;

if(dp[a][b]!=-1) return dp[a][b];

if(a==0 || b==0) return 1;

else

{

lli ret=(solve(a-1,b)+solve(a,b-1))%mod;

dp[a][b]=ret;

return ret;

}

}

int main()

{

int t;

cin>>t;

memset(dp,-1,sizeof dp);

// solve(26,26);

for(int i=0;i<=26;i++)

{

for(int j=0;j<=26;j++)

{ dp[i][j]= solve(i,j);

// cout<<dp[i][j]<<endl;

}

}

// cout<<dp[24][3]<<" "<<dp[3][24]<<endl;

 while(t--)

 {

    int a,b;

    cin>>a>>b;

    if(a>b) swap(a,b);

   if((abs(a-b)>2  && b>25)||(a<=24 && b<=24) ||(a==b) || (abs(a-b)==1))

     {

      cout<<0<<endl;

}

else if(b==25) 

{

cout<<dp[a][b-1]<<endl;

}

else

{

lli ans=power(2,min(a,b)-24);

ans=(ans*dp[24][24])%mod;

while(ans<0)ans+=mod;

cout<<ans<<endl;

}

 }

}