Problem statement
Contest source
Author, Editorialist : Abhinav
Tester : Miten Shah
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;
}