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 ??
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 14:02:40 (h1).
Desktop version, switch to mobile version.
Supported by
What are limits on
n?1 <= n <= 1e6
Because
If there is a prime modulo you can use Modular Inverse with O(n) precalculation finding Factorial[] and Inverse_Factorial[]
The formula:
Then you can calculate the rest in O(sqrt n)
Total time complexity: O(n)
Total space complexity: O(n)
I don't think there exist any algo better than this one. Sqrt(N) + O(N) will be best probably.
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.
Let $$$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.
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
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.