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

Before contest

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

11:41:11

Register now »

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

11:41:11

Register now »

*has extra registration

By Shayan

Before stream
14:36:10

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 161 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 154 |

5 | -is-this-fft- | 148 |

5 | SecondThread | 148 |

7 | Petr | 147 |

7 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 05:53:50 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

What are limits on

`n`

?1 <= n <= 1e6

Because

If there is a prime modulo you can use

Modular InversewithO(n)precalculation findingFactorial[]andInverse_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.

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))$$$).

Thisproblem 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.

Code for calculating nCr in O(1) with O(n) precomputations