Chef and Trump Cards (CRDGAME2) - Video EDITORIAL

Question Link - https://www.codechef.com/SEPT20A/problems/CRDGAME2
Solution Link - https://www.codechef.com/viewsolution/37839080

Editorial - https://www.youtube.com/watch?v=VDVOJNo57RQ

C++

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1000000007;
int powr(int x,int y){
if(y==0){
return 1;
}
int h = powr(x,y/2);
int f = (hh)%mod;
if(y&1){
f = (f
x)%mod;
}
return f;
}
int fact(int n){
int prod = 1;
for(int i = 2;i<=n;++i){
prod = (prod*i)%mod;
}
return prod;
}
int Comb(int n,int r){
/// return fact(n)/(fact®*fact(n-r));
int num = fact(n);
int den = (fact®fact(n-r))%mod;
int denInverse = powr(den,mod-2);
return (num
denInverse)%mod;
}
int32_t main(){
int T;
cin>>T;
while(T–){
int N;cin>>N;
int C[N];
map<int,int>freq;
for(int i = 0;i<N;++i){
cin>>C[i];
freq[C[i]]+=1; ///maximum frequency
}
int f = freq.rbegin()->second;
int possible_draws = 0;
if(f&1){

    }
    else{
        int equally = f/2;
        ///fC(f/2) * pow(2,N-f)
        int left = Comb(f,f/2);
        int right = powr(2,N-f);
        possible_draws = (left*right)%mod;
    }
    int total_ways_to_divide = powr(2,N);
    cout<<(mod+(total_ways_to_divide-possible_draws))%mod<<"\n";
}

}

1 Like