Subsequence product !!! NMNMX - NO MINIMUM NO MAXIMUM
Old school indeed... thats the fortran power op as well.
I can't follow the link. But powers often mean logs; can you re-write the problem in a log equation that makes it work?
I can't follow the link. But powers often mean logs; can you re-write the problem in a log equation that makes it work?
this looks like the other thread from honeybuzz. I also got TLE for the harder cases. I think sometimes that site is a little insane in its reqs -- even with some optimizations they've still managed to create a series of ridic tests. They also have old versions for some of the other languages.
For the modulus thing, pseudo-code (maybe Ruby code :D), with x being the big prime, prod being your product and ele an element, instead of
you can do
should be same result. For C++, "prod" will likely need to be a long (perhaps even long long) to withstand a multiplication greater than int range.
For the modulus thing, pseudo-code (maybe Ruby code :D), with x being the big prime, prod being your product and ele an element, instead of
x = 1000000007 prod *= ele**5 prod %= x |
you can do
x = 1000000007
prod = 1
ele = 12
5.times {
prod *= ele
prod = prod%x if prod>x
} |
should be same result. For C++, "prod" will likely need to be a long (perhaps even long long) to withstand a multiplication greater than int range.
@Kr002 you can calculate
In this case,
(a^b)%m,where m is a prime number and b is large by reducing b. This can be done by making b=b%phi(m), where phi(m) is the Euler totient(http://mathworld.wolfram.com/TotientFunction.html) of m.In this case,
m is a prime, so phi(m)=m-1. Now all you need to do is calculate nCr normally or using dp table and each time just do nCr%(m-1). Now your exponent b has been reduced and you can simply calculate (a^b)%m using modular exponentiation(https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/).
@Kr002 are you considering the value of k while calculating the combinations?because I am getting WA
Ah then that's why I am getting WA...Can you give me a hint to find the combinations?Also, did the toitent function help?
@helpinghand the problem is that the nCr values are going to be very large...Examples - 4500C10....
@Kr002 did you get 100pts?Also, when should I take modulo?@helpinghand said to "calculate nCr normally" and then apply euler totient...But calculating nCr normally itself would yield a very very big number!!!Please help!
i can say that no. of occurences of ith element in the subsequences equal to (n-1)C(k-1)-
(n-i)C(k-1)-(i-1)C(k-1).
now what else pattern to be noticed in this calculation of ncr for all the no.s.?
Can it be written in simpler way?
(n-i)C(k-1)-(i-1)C(k-1).
now what else pattern to be noticed in this calculation of ncr for all the no.s.?
Can it be written in simpler way?
@needbro how did you derive the above formula?I am using the inclusion exclusion principle for the combinations
Last edited on
let's take the case that total no. of times element a[i] can be included in all the subsequences of k length:
it will be like, we have fixed one element(i.e a[i]) and now we have to select k-1 from remaining n-1,which is same as (n-1)C(k-1).
now,
let's count how many subsequences will have a[i] as the first element:
it will be (n-i)C(k-1):
and then ,let's count how many subsequences will have a[i] as the last element:
it will be (i-1)C(k-1).
{ofcourse u need to sort the array before applying these.}
it will be like, we have fixed one element(i.e a[i]) and now we have to select k-1 from remaining n-1,which is same as (n-1)C(k-1).
now,
let's count how many subsequences will have a[i] as the first element:
it will be (n-i)C(k-1):
and then ,let's count how many subsequences will have a[i] as the last element:
it will be (i-1)C(k-1).
{ofcourse u need to sort the array before applying these.}
@helpinghand thank u so much...your suggestion for using Euler's totient was very useful!
@needbro i am applying same but getting wrong answer.
please help
also are u taking value of index i from 1??
please help
also are u taking value of index i from 1??
i have the same problem as Anonymous has.
In our formula n value of nCr is not fixed.
so is there any other simplification of that formula, so that n gets fixed?
any help will be appreciated...
In our formula n value of nCr is not fixed.
so is there any other simplification of that formula, so that n gets fixed?
any help will be appreciated...
I have the correct logic and have applied a lot of optimizations but am getting TLE in last 2 test cases :/
is there any other simplification of my formula, so that n gets fixed?
any help will be appreciated...
any help will be appreciated...