i came acrross weird queries problem on code chef .
Here is the link to it
I found a good solution for the same .But i could not understand it .It would be nice if anyone could explain this . Here is the code..........
#include <iostream>
#include<vector>
using namespace std;
const int md = 1000000007;const int MAX = 10010;
const int SOM = 100010;
const int N = 500010;int a[N];
int *p = &a[N];
vector<int> occ[N];
int PREC[MAX][MAX / 2];
int fact[SOM], invfact[SOM];
inline int add(int &a, int b)
{
a += b;
if (a >= md)
{
a -= md;
}
}
inline int mul(int a, int b)
{
return (long long)a * b % md;
}
inline int pw(int a, int b)
{
if (b == 1)
{
return a;
}
if (b == 2)
{
return (long long)a * a % md;
}
int res = 1;
while (b > 0)
{ if (b & 1)
{
res = mul(res, a);
if (b == 1)
{
break;
}
}
a = mul(a, a);
b >>= 1;
}
return res;
}
inline int inv(int x)
{
return pw(x, md - 2);
}
inline int C(int n, int k)
{
k = min(k, n - k);
if (n <= 10000)
{
return PREC[n][k];
}
return mul(fact[n], mul(invfact[k], invfact[n - k]));
}
int main()
{
printf("program started to function \n");
fact[0] = 1;
invfact[0] = 1;
for (int i = 1; i < SOM; i++)
{
fact[i] = mul(fact[i - 1], i);
invfact[i] = inv(fact[i]);
}
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX / 2; j++)
{
if (j == 0)
PREC[i][j] = 1;
else if (i == 0)
PREC[i][j] = 0;
else
{
PREC[i][j] = PREC[i - 1][j] + PREC[i - 1][j - 1];
if (PREC[i][j] >= md)
PREC[i][j] -= md;
}
}
}
int m, tt;
printf("\n Enter the array size and no of queries:");
scanf("%d %d", &m, &tt);
for (int i = 0; i < N; i++)
{
occ[i].clear();
}
printf("\n Enter the array elements");
for (int i = 0; i < m; i++)
{
scanf("%d", a + i);
occ[a[i]].push_back(i);
}
vector<int> diff;
for (int i = 0; i < N; i++)
{
if (!occ[i].empty())
{
diff.push_back(i);
}
}
while (tt--)
{
int l,r, n, k;
printf("\n Enter query params");
scanf("%d %d %d %d",&l,&r, &n, &k);
printf("\n Printing query params:");
printf("\n values of l r n k is: \t %d %d %d %d",l,r,n,k);
if (n == 0)
{ printf("\n n value is 0");
printf(" \n %d", 1);
continue;
}
if ((n - 1) * 1LL * (k - 1) > 1e9)
{
printf("%d\n", 0);
continue;
}
int sub = (n - 1) * (k - 1);
printf("\n Sub value : %d", sub);
int ans = pw(fact[n], r - l);
printf("\n Ans value after pw function:%d",ans);
for (int i = 0; i < (int)diff.size(); i++)
{
int num = diff[i];
int cnt = lower_bound(occ[num].begin(), occ[num].end(), r + 1) -
lower_bound(occ[num].begin(), occ[num].end(), l);
if (cnt == 0)
{
continue;
}
int x = num - sub;
int y = n;
if (x < y)
{
ans = 0;
break;
}
int z = C(x, y);
ans = mul(ans, pw(z, cnt));
}
printf("\n Answer is : %d", ans);
}
return 0;
}
What I have tried:
i have given some comments which is what i could understand.
question link:
Contest Page | CodeChef[
^]