### harshalpamecha3's blog

By harshalpamecha3, history, 4 months ago,

• -5

 » 4 months ago, # | ← Rev. 3 →   0 Do you recall the combinactories problem in your high school, where there are total $n$ items and $n1$, $n2$, $n3$,$...$ different items in a bag. Then what are the different combinations of choosing items from the bag. It was- ($n!$)/($n1!$*$n2!$*$n3!$$...) Similarly, consider this problem same too. You have been given a number n and you have n different(maybe same) digits. Find the total ways to choose is. Simply find the frequency of all digits and find (n!)/(n1!*n2!*n3!$$...$), where $n1$, $n2$, $n3$ are the frequencies.
•  » » 4 months ago, # ^ |   0 But here constraint are high so how to calculate factorial???
•  » » » 4 months ago, # ^ |   0 Precompute Codeint fact[N], invfact[N]; int modinv(ll k) { return power(k, mod1-2, mod1); } void precompute() { fact[0]=fact[1]=1; for(int i=2;i=0;i--) { invfact[i]=invfact[i+1]*(i+1); invfact[i]%=mod; } } int nCr(ll x, ll y) { if(y>x) return 0; int num=fact[x]; num*=invfact[y]; num%=mod; num*=invfact[x-y]; num%=mod; return num; } 
•  » » » » 4 months ago, # ^ |   0 Thank You
•  » » » 4 months ago, # ^ |   0 Basically you can be given a number having maximum of 10^5 digits. Each character(digit) can only be from 0 to 9. So, you store frequency of each digit in an array of size 10. Now, again when you apply the permutation formula you may have to calculate factorial of 10^5 but we need to report answer as modulo mod(prime number given). So, basically all of your precomputed factorial values will not go beyond mod value because you will be storing them by taking modulo with respect to mod. Similarly you have to store inverse-factorial values also upto 10^5 modulo mod(read about Using FERMET's Little Theorem for finding Modular Multiplicative Inverse if you dont know yet). Doing these modular arithmatic calculations you can evaluate the above mentioned expression. Time and Space Complexities would be -> O(n) where n = 10^5.
•  » » » » 4 months ago, # ^ |   0 Thank you!!