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
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 (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 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.?
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...