| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 1 | maomao90 | 161 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | atcoder_official | 148 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 10 | TheScrasse | 142 |
Hello CF community, I'm trying to solve this problem, the problem tells me that I have to calculate
in the numerator it will always be $$$\prod _{i = N-M+1}^{n} i$$$ and in the denominator will be $$$ \prod _{i=1}^{min(N, N-M)}i$$$ as the rest will cancel out
and this is my code:
but it gives me WA, I'm not really sure why I'm getting this. Any ideas?
The problem is to calculate a binomial coefficient.
USACO — How to implement this
Wikipedia — More about binomial coefficients
Thank you!.
I've already seen that there are others methods to solve this, however, I want to know what's wrong in my code, I tried to search on YouTube and I saw a guy wrote the same code and had AC
Well, maybe there is an overflow in ans or dAns variable.
but how this dude got AC, watch this @$$$15:20$$$, it's the very same code
Two things I noticed:
dAns? You know that the result is integral, and you've already done all the division using the gcd trick. So I thinkdAnsis completely unecessary.For point no.1 you mentioned: for $$$N=100, M=40$$$ for example you want be sure to get rid of the $$$max(M!, (N-M)!)$$$ $$$\frac{100!}{40!\cdot (100-40)!}$$$ you want to cancel $$$60!$$$ to reduce the multiplicated numbers so you divide on the $$$min$$$ between them, in other words you have to divide on one of them and cancel the other, so you choose the $$$max$$$ to be cancelled from the numerator and denominator and divide on the $$$min$$$.
For point no.2: you need
dAnsin case there's a number $$$x$$$ in the denominator such that $$$gcd(x,y_i)=1$$$ for $$$0 \leq i\leq nn.size()$$$For $$$N = 100$$$ and $$$M = 60$$$ you are currently using $$$\prod_{i = N - M + 1} ^ {N} i = \frac{N!}{(N - M)!} = \frac{100!}{40!}$$$ for the numerator. For the denominator you are using $$$\prod_{i = 1} ^ {min(M, N - M)} i = 40!$$$. This is wrong.
I still dont see any reason to keep
dAns. Thinking about it,dAnsis always going to be 1.For $$$N=100$$$ and $$$M=60$$$, the numerator would be just $$$61\times 62\ldots \times 100$$$, even if
dAnsisn't necessary, I don't understand why it's WA, can you modify my code please?Also, you may see the YouTube video in previous commens that wrote the same code and had AC
As I was saying in my original comment, you are erroneously using
minfor the formula for the numerator. Read through the code in the youtube video again, its calculation for the numerator is different from your code. The youtube code doesn't involve callingminwhen calculating the numerator.My advice is to use a pen and paper, write down the definition for binomial coefficient, and then from that extract the expression for the numerator and denominator. You will see that you don't need to have any mins or maxes anywhere.
I've already done, and when I didn't reach any solutions (except this) I posted this blog.
Anyway thank you!
It did work!!!
I was mistaken in formatting the output, I commented
if(m == n){cout << 1 ; continue;}and it worked like magic
In the first for loop, replace
n-m+1withn-min(m, n-m)+1.Could you explain the difference please?
What a text editor do you use ?
If you're asking about the photo I used this site to generate a beautiful snapshot of the code.
Thanks a lot !