#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
#define MX 500002
unsigned long long power(ll x, ll y)
{
unsigned long long res = 1;
x = x % MOD;
while (y > 0) {
if (y & 1)
res = (res * x) % MOD;
y = y >> 1; // y = y/2
x = (x * x) % MOD;
}
return res;
}
unsigned long long modInverse(ll n)
{
return power(n, MOD - 2);
}
unsigned long long NcR(ll n, ll r)
{
if (r == 0)
return 1;
unsigned long long fac[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % MOD;
return (fac[n] * modInverse(fac[r]) % MOD * modInverse(fac[n - r]) % MOD) % MOD;
}
void solve(){
ll n;
cin>>n;
ll A[n+1];
for(int i=0;i<n;i++)
cin>>A[i];
ll Frq[n+1];
memset(Frq, 0 ,sizeof(Frq));
for(int i=0;i<n;i++)
Frq[A[i]]++;
ll res[n+1];
vector<ll> get[n+1];
for(ll i=1;i<=n;i++)
{
ll prev = 0;
get[i].push_back(0);
for(ll j=1;j<=Frq[i];j++){
ll nc = NcR(Frq[i], j)%MOD;
get[i].push_back( (prev + nc)%MOD);
prev += nc;
prev%=MOD;
}
}
// for(ll i=1;i<=n;i++)
// {
// for(auto x:get[i])
// cout<<x<<" + ";
// cout<<"\n";
// }
for(ll i=1;i<=n;i++)
{
ll prod;
ll rs = 0;
for(ll j = 1;j<= Frq[i];j++){
prod = NcR(Frq[i] , j)%MOD;
for(ll k = 0;k<=n;k++)
{
if(Frq[k]!=0)
{if(k < i){
ll add = 0;
add += get[k][min(j-1 , Frq[k])]%MOD;
add+=1LL;
prod *= add%MOD;
prod %=MOD;
}else if (k >i){
ll add = 0;
add += get[k][min(j , Frq[k])]%MOD;
add+=1LL;
prod *= add%MOD;
prod %=MOD;
}
}
}
rs += prod%MOD;
}
res[i] = rs%MOD;
}
for(ll i=1;i<=n;i++)
cout<<(res[i]%MOD)<<" ";
cout<<"\n";
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
test;
return 0;
}
Where am I going wrong for subtask 1, probably Modulo?
https://www.codechef.com/viewsolution/36854165
CodeChef: Practical coding for everyone can anyone tell me where am I getting wrong for atleast 10 points in the question SUBSFREQ
Take this as your custom input
1
3
3 2 1
your answer would be 1 2 4
but its wrong , it should be 4 2 1 .
And even if custom input is
1
3
1 2 3
Then also answer is 4 2 1 .
For each test case, print a single line containing NN space-separated integers. For each valid i, the i-th of these integers should be the number of occurrences of i on Chef’s sheet of paper.
The chefs write down is a bit different from what u took .
Read the above para carefully you will get it
1 Like