Problem statement

Contest source

* Author, Editorialist :* Abhinav

*Miten Shah*

**Tester :**# DIFFICULTY:

easy-medium

# PREREQUISITES:

math, combinatorics

# PROBLEM:

Two people are fighting. We have to find the no. of fights possible where either of them dies in each round, and one of them can resurrect N times with a condition that he cannot die more than once consecutively, and the other one can resurrect M times with no condition.

# EXPLANATION:

*Note: Faizal cannot die twice consecutively, if Faizal dies, it is necessary for Faizal to win the next round to win the fight.*

Let’s first find the number of ways for Faizal to win, then we will find the no. of ways to lose, and add them.

### For winning:

Let’s iterate, over all the number of times Faizal can resurrect (i = 0 to n) ,

Ex: If i=4, (let’s denote Faizal’s death by F and win by S, there will be at least one S just after F, as it is necessary for Faizal to win the next round so we group F and S together i times and find the number of ways to distribute S at the remaining places.)

\_ FS\_FS\_FS\_FS\_ (for i=4, we have 5 places, where we have to place S, so that the total sum of S is equal to m+1, as Sultan can resurrect m times, he must die m+1 times for Faizal to win), so the number of ways to win is equal to number of ways to place distribute (m+1-i) S numbers among (i+1) groups = ^{(m+1-i) + (i+1) -1}C_{(i+1) - 1} = ^{m+1}C_{i}, we calculate this for each i = 0 to n and sum them up.

### For losing:

We can do a similar thing to find the number of ways Faizal can lose:

We iterate for each i=1 to n+1, (we calculate the number of ways Faizal lose when he dies exactly i+1 times, where he dies twice consecutively at the last time)

Ex: If i=4, for Faizal to lose he has to die in the last two rounds consecutively, \_FS\_FS\_FS\_FF , we calculate the number of ways to distribute \leq (m-(i-1)) S at among i groups = ^{(m-i+1) + i}C_{i} = ^{m+1}C_{i} and sum them up.

Note: There is a case where Faizal can lose even without consecutively dying twice, we can count that case separately (if n=5, it will be in the form of \_FS\_FS\_FS\_FS\_FS\_F) or we can just consider it like like the case where he dies n+2 times \_FS\_FS\_FS\_FS\_FS\_FF).

# SOLUTION :

## C++ Solution (Linear)

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,N=2e5+4;
int fact[N],factInv[N];
int binexp(int a,int b){
a%=mod;
int res=1;
while(b){
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int ncr(int n,int r){
if(r>n)
return 0;
return fact[n]*factInv[r]%mod*factInv[n-r]%mod;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
fact[0]=1;
for(int i=1;i<N;i++)
fact[i]=fact[i-1]*i%mod;
factInv[N-1]=binexp(fact[N-1],mod-2);
for(int i=N-1;i>0;i--)
factInv[i-1]=factInv[i]*i%mod;
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int win=0;
for(int i=0;i<=n;i++){
int N=m+1-i,R=i+1;
win+=ncr(N+R-1,R-1);
win%=mod;
}
int loss=0;
for(int i=1;i<=n+1;i++){
int N=m-i+1,R=i;
loss+=ncr(N+R,R);//ncr(N+R-1,R-1) + ncr(N+R-2,R-1) + .... ncr(R-1,R-1)
loss%=mod;
}
int ans=(win+loss)%mod;
cout<<ans<<'\n';
}
}
```

## C++ Tester's Solution

```
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int max_n = 1e5;
const int sum_max_n = 1e6;
const int max_k = 2e3;
const ll M = 1000000007;
const ll N = 100005;
ll power(ll a,ll n,ll m=M){
ll ans=1;
while(n){
if(n&1) ans=ans*a;
a=a*a;
n=n>>1;
ans=ans%m;
a=a%m;
}
return ans;
}
ll f[N], invf[N];
void pre(){
f[0] = 1;
rep(i,1,N) f[i] = (f[i-1] * i) % M;
rep(i,0,N) invf[i] = power(f[i], M-2) % M;
}
// factorial
ll ncr(ll n,ll r,ll m=M){
return (f[n] * ((invf[r] * invf[n-r]) % M)) % M;
}
void solve(ll n, ll m){
ll ans = 0;
rep(i,0,min(n+1,m+2)){
ans = (ans + ncr(m+1,i));
}
rep(i,1,n+2){
ll k = m-i+1;
if(k<0) break;
ans = (ans + ncr(m+1,i)) % M;
}
cout << ans << endl;
return;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll no = readIntLn(1, max_k);
// no = 1;
pre();
ll sum_n = 0, sum_m = 0;
while(no--){
ll n = readIntSp(0, max_n), m = readIntLn(0, max_n);
sum_n += n;
sum_m += m;
solve(n,m);
}
assert(sum_n <= sum_max_n);
assert(sum_m <= sum_max_n);
assert(getchar()==-1);
return 0;
}
```