 # VKMWED - Editorial

Author, Editorialist : Abhinav
Tester : Miten Shah

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=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 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){
}
long long readIntLn(long long l,long long 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 = 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);
// no = 1;
pre();
ll sum_n = 0, sum_m = 0;
while(no--){
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;
}

3 Likes

the number of ways to distribute m-(i-1) i.e (m+1-i) S at among i groups should be C(m,i-1) ??
Please tell me where I’m wrong.

The formula states that the number of ways to distribute N identical objects into R groups is
C(N+R-1,R-1).
N object into R groups

You have to distribute <=(m+1-i) S, not only (m+1-i) S.

In Solution(Linear), how did you get ncr(N+R,R) = ncr(N+R-1,R-1) + ncr(N+R-2,R-1) + … ncr(R-1,R-1) ?

we calculate the number of ways to distribute \leq≤ (m-(i-1))(m−(i−1)) SS at among ii groups = (m−i+1)+iCi, please can you explain this like I want to place n identical object into r groups then the solution is (n-1+r)C(r-1), but in this case, you didn’t do ((m−i+1)+i-1)C(i-1) why is that??

For winning shouldn’t it be exactly m+1-i ?

yes, formula is correct, but we are distributing it in i+1 group not i group.
we are distributing m-i+1 S among i+1 groups in winning case = m+1Ci
for the losing case we are distributing <= (m+1-i) (i.e. 1,2,3,…,m+1-i) S among i groups = m+1Ci

<= (m-(i-1)) means we have to count all the cases where we distribute 1,2,3,4,…m-(i-1) S among i groups, if we solve them separately and add them up, we get m+1Ci.