### darkworld1's blog

By darkworld1, history, 4 years ago,

you have given N. you need to find out C(n,1*1)+C(n,2*2)+C(n,3*3)+c(n,4*4) + .....
Here c(n,r) = n!/((n-r)!*(r)!)
one way is find C(n,i*i) for all i between 1 <= i <= sqrt(n)
. Is there exist any efficient solution than this ??

• +13

| Write comment?
 » 4 years ago, # |   0 What are limits on n?
•  » » 4 years ago, # ^ |   0 1 <= n <= 1e6
 » 4 years ago, # | ← Rev. 9 →   +14 Because $1 \leq n \leq 10^6$If there is a prime modulo you can use Modular Inverse with O(n) precalculation finding Factorial[] and Inverse_Factorial[]The formula: $C(n, k) = n! / ((n — k)! \times k!) = n! \times inverse(n-k)! \times inverse(k)! = Factorial[n] \times Inverse\_Factorial[n — k] \times Inverse\_Factorial[k]$Then you can calculate the rest in O(sqrt n)Total time complexity: O(n)Total space complexity: O(n)
 » 4 years ago, # |   0 I don't think there exist any algo better than this one. Sqrt(N) + O(N) will be best probably.
•  » » 4 years ago, # ^ | ← Rev. 6 →   +13 Actually, you can solve this problem in $O(\sqrt{n} \cdot \log^3 n)$ time (I suppose that we want to find this value modulo some relatively small prime $p$, where by "relatively small" I mean $p = n^{O(1)}$). The main idea is the same as in the standard algorithm for calculating $n!$ in $O(\sqrt{n} \log^2 n)$ time, which is reproduced in the spoiler below. Calculating n! quickly via multi-point evaluationLet $k := \lfloor \sqrt{n} \rfloor$. It is enough to calculate $(k^2)!$, because we can deal with the remaining $O(\sqrt{n})$ multipliers naively. Notice that $(k^2)! = (1 \cdot 2 \cdot \ldots \cdot k) \cdot ((k + 1) \cdot (k + 2) \ldots \cdot (k + k)) \cdot ((k^2 - k + 1) \cdot (k^2 - k + 2) \cdot \ldots k^2)$ $= P(0) \cdot P(k) \cdot P(2k) \cdot \ldots \cdot P(k^2 - k)$, where $P(x) = (x + 1) \cdot (x + 2) \cdot \ldots \cdot (x + k)$. We can calculate the coefficients of the polynomial $P(x)$ in $O(k \log^2 k)$ time by divide-and-conquer and FFT. After that, we need to evaluate $P$ in $k$ points quickly. It is also a standard problem (usually called "multi-point evaluation") and it can be solved in $O(k \log^2 k)$ time as well.Denote $k := \lfloor \sqrt{n} \rfloor$. Our problem can be reduced to calculating two factorials ($n!$ and $(n - k^2)!$) and two instances of "calculate the products on contiguous ranges of integers with lengths $1$, $3$, $5$, $\ldots$, $(2k + 1)$" (for example, $(i^2)! = ((i-1)^2)! \times ((i^2 - 2i + 2) \cdot \ldots \cdot (i^2 - 1) \cdot (i^2))$). This problem can be reduced to two instances of "calculate the products on contiguous ranges of integers with lengths $0$, $1$, $2$, $\ldots$, $k$").Okay, let's solve the latter problem recursively. We want to calculate $s_1$, $s_2 \cdot (s_2 + 1)$, $\ldots$, $s_\ell \cdot (s_\ell + 1) \ldots (s_\ell + \ell - 1)$ for some integers $s_i$. Suppose for simplicity that $\ell$ is odd and $\ell = 2m+1$. Consider the polynomial $P(x) = x \cdot (x + 1) \cdot (x + m)$. We can find $P(s_{m + 1})$, $P(s_{m + 2})$, $\ldots$, $P(s_{\ell})$ in $O(\ell \log^2 \ell)$ time by the same multi-point evaluation trick. It remains to find some products on ranges with lengths $1$, $2$, $\ldots$, $m$, $(m + 1) - (m + 1) = 0$, $(m + 2) - (m + 1) = 1$, $\ldots$, $(2m + 1) - (m + 1) = m$. Thus, we reduced our problem to two smaller problems (for $m$ ranges instead of $\ell$). Therefore, the time complexity satisfies the reccurence $T(\ell) = 2T(\ell/2) + O(\ell \log^2 \ell)$. Hence, $T(\ell) = O(\ell \log^3 \ell)$.Finally, the whole algorithm takes $O(T(k)) = O(\sqrt{n} \cdot \log^3 n)$ time.P. S. I wouldn't be surpised if it is possible to shave the extra logarithm (as compared to calculating $n!$) off somehow.
•  » » » 4 years ago, # ^ |   0 Kaban-5 for N <= 10^6, O(N) will be better than O(sqrt(N)*log3N). and also the mentioned solution need much constant factor optimisations. however I believe it might work for larger constraints :) THanks
 » 4 years ago, # | ← Rev. 3 →   0 As one of the comments already mentions, using the inverse modulo of the factorial in the denominator would work. I wrote code for this problem in which I had to find the sum of combinations, although not the same ones. Code for calculating nCr in O(1) with O(n) precomputations#define MOD 1000000007LL const int MAXN = 1e6+10; ll fact[MAXN], invFact[MAXN]; ll power(ll base, ll exp) { if(!exp) return 1LL; ll ans = power(base, exp>>1LL); ans = (ans*ans)%MOD; if(exp & 1LL) ans = (ans*base)%MOD; return ans; } ll nCr(ll n, ll r) { ll ans = fact[n]; ans = (ans*invFact[r])%MOD; ans = (ans*invFact[n-r])%MOD; return ans; } int main() { ll n, m; cin>>n>>m; fact[0] = invFact[0] = 1LL; FOR(i, 1, m+1) fact[i] = (fact[i-1]*i)%MOD, invFact[i] = power(fact[i], MOD-2LL); return 0; }