I was doing a question Advertising Agency [Your text to link here...](https://mirror.codeforces.com/problemset/problem/1475/E)↵
where i need to find NcR but if N is very large i had to use modulo of 10^9+7 but for some reason my answer gets wrong on test 6 where n is very big. I think the problem is not using modulo properly but i cant figure it out.↵
[problem:1475E][submission:121841381]↵
any help is appreciated.↵
In my code n=to and r=bef;↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include <iostream>↵
using namespace std;↵
↵
//#include <chrono>↵
//using namespace std::chrono;↵
↵
long long multi(long long a, long long b, long long mod){↵
return (a * b) % mod;↵
}↵
↵
long long power(long long a, long long b, long long mod){↵
long long powans = 1;↵
↵
for(; b > 0; a = multi(a, a, mod), b /= 2) if(b % 2 == 1) powans = multi(powans, a, mod);↵
↵
return powans;↵
}↵
↵
void fastscan(int &x)↵
{↵
bool neg=false;↵
register int c;↵
x =0;↵
c=getchar();↵
if(c=='-')↵
{↵
neg = true;↵
c=getchar();↵
}↵
for(;(c>47 && c<58);c=getchar())↵
x = (x<<1) + (x<<3) +c -48;↵
if(neg)↵
x *=-1;↵
}↵
↵
int gcd(long long int a,long long int b){↵
if(a%b==0)↵
return b;↵
else↵
return gcd(b,a%b);↵
}↵
long long int fact(long long int to,long long int bef){↵
long long sol=1;↵
if(to-bef<bef)↵
bef=to-bef;↵
long long int p=bef;↵
long long int n=1,d=1;↵
while(p--){↵
n=n*to%1000000007;↵
d=d*bef%1000000007;↵
long long int m=gcd(n,d);↵
n=n/m;↵
d=d/m;↵
n=n%1000000007;↵
d=d%1000000007;↵
to--;↵
bef--;↵
}↵
return n;↵
}↵
↵
void solve(){↵
int n,k;↵
cin>>n>>k;↵
int arr[n];↵
for(int i=0;i<n;i++)↵
cin>>arr[i];↵
sort(arr,arr+n,greater<int>());↵
int value=arr[k-1];↵
long long int bef=0,to=0;↵
for(int i=0;i<n;i++){↵
if(arr[i]==value){↵
to++;↵
if(i<=k-1)↵
bef++;↵
}↵
}↵
long long int sol=1;↵
sol=fact(to,bef);↵
cout<<sol%1000000007<<endl;↵
}↵
int main(){↵
↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt","r",stdin);↵
freopen("output.txt","w",stdout);↵
freopen("error.txt","w",stderr);↵
#endif↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
//auto start = high_resolution_clock::now();↵
int t;↵
cin>>t;↵
while(t--) {↵
solve();↵
}↵
// auto stop = high_resolution_clock::now();↵
// auto duration = duration_cast<microseconds>(stop - start);↵
// cout << duration.count() << endl;↵
return 0;↵
}↵
~~~~~↵
↵
where i need to find NcR but if N is very large i had to use modulo of 10^9+7 but for some reason my answer gets wrong on test 6 where n is very big. I think the problem is not using modulo properly but i cant figure it out.↵
[problem:1475E][submission:121841381]↵
any help is appreciated.↵
In my code n=to and r=bef;↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include <iostream>↵
using namespace std;↵
↵
//#include <chrono>↵
//using namespace std::chrono;↵
↵
long long multi(long long a, long long b, long long mod){↵
return (a * b) % mod;↵
}↵
↵
long long power(long long a, long long b, long long mod){↵
long long powans = 1;↵
↵
for(; b > 0; a = multi(a, a, mod), b /= 2) if(b % 2 == 1) powans = multi(powans, a, mod);↵
↵
return powans;↵
}↵
↵
void fastscan(int &x)↵
{↵
bool neg=false;↵
register int c;↵
x =0;↵
c=getchar();↵
if(c=='-')↵
{↵
neg = true;↵
c=getchar();↵
}↵
for(;(c>47 && c<58);c=getchar())↵
x = (x<<1) + (x<<3) +c -48;↵
if(neg)↵
x *=-1;↵
}↵
↵
int gcd(long long int a,long long int b){↵
if(a%b==0)↵
return b;↵
else↵
return gcd(b,a%b);↵
}↵
long long int fact(long long int to,long long int bef){↵
long long sol=1;↵
if(to-bef<bef)↵
bef=to-bef;↵
long long int p=bef;↵
long long int n=1,d=1;↵
while(p--){↵
n=n*to
d=d*bef
long long int m=gcd(n,d);↵
n=n/m;↵
d=d/m;↵
n=n%1000000007;↵
d=d%1000000007;↵
to--;↵
bef--;↵
}↵
return n;↵
}↵
↵
void solve(){↵
int n,k;↵
cin>>n>>k;↵
int arr[n];↵
for(int i=0;i<n;i++)↵
cin>>arr[i];↵
sort(arr,arr+n,greater<int>());↵
int value=arr[k-1];↵
long long int bef=0,to=0;↵
for(int i=0;i<n;i++){↵
if(arr[i]==value){↵
to++;↵
if(i<=k-1)↵
bef++;↵
}↵
}↵
long long int sol=1;↵
sol=fact(to,bef);↵
cout<<sol%1000000007<<endl;↵
}↵
int main(){↵
↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt","r",stdin);↵
freopen("output.txt","w",stdout);↵
freopen("error.txt","w",stderr);↵
#endif↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
//auto start = high_resolution_clock::now();↵
int t;↵
cin>>t;↵
while(t--) {↵
solve();↵
}↵
// auto stop = high_resolution_clock::now();↵
// auto duration = duration_cast<microseconds>(stop - start);↵
// cout << duration.count() << endl;↵
return 0;↵
}↵
~~~~~↵
↵
