Блог пользователя silent__killer1

Автор silent__killer1, история, 5 лет назад, По-английски

Hi ,I need to compute ncr for (n) from 1<=n<=1e9 where (n-r) are from 1<=n-r<=1e6 . Mod 1e9+7.I googling about this and get to know that this could be done by (lucas theorem) I try to implement but fails . So if anyone could help me in this it would be grateful.And please share your code for this.Thankyou.

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

What is ncr?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

I don't know if this is fast enough for your case but it might be:

  1. Write a brute force program to compute all factorials of the form $$$y!$$$ such that $$$y$$$ is a multiple of $$$X$$$ and put them in a static array $$$Y$$$ in your real program.
  2. To compute any factorial of the form $$$z!$$$, find the largest element $$$e$$$ of the form $$$k!$$$ in $$$Y$$$ such that $$$k \leq z$$$, and then iterate from $$$k+1$$$ to $$$z$$$ and multiply all these numbers by $$$e$$$.

The complexity of calculating any NCr would be $$$O(X)$$$ and the memory complexity (for the static array) would be $$$O(\frac{N}{X})$$$, so maybe $$$X = 10^6$$$ is enough.

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +39 Проголосовать: не нравится

I don't understand why this problem is so hard. I think it is fairly easy. Notice the constraint $$$n-r \le 10^6$$$. You can easily calculate value of $$$C(n,r)$$$ in $$$O(r)$$$. For further explanation, see hint.

Hint

Lastly, you need to remember that $$$C(n,r) = C(n,n-r)$$$, hence if $$$n-r \le 10^6$$$, then you should calculate $$$C(n,n-r)$$$ instead of calculating $$$C(n,r)$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Didn't get the last part...

    https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/ Why this : if ( k > n — k ) k = n — k;

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      That is exactly what I wrote in the last line.

      Since $$$C(n,r) = C(n,n-r)$$$, it means, when calculating $$$C(n,k)$$$, if $$$ n-k < k $$$, then it is better ( faster ) to calculate $$$C(n,n-k)$$$, assuming you are using a linear algorithm.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        If i use k as k even if k>n-k, will it work ?

        It's giving me WA on this problem if i dont replace k with n-k if k>n-k

        https://www.spoj.com/problems/MARBLES/ (code: https://ide.codingblocks.com/s/142841)

        Thanks!

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

          Well, you need to understand that $$$(n-i+1)/i$$$ might not always be an integer. You might be losing precision, due to integer division. Honestly, I don't understand how putting that line is giving you an AC.

          Also, calculating the whole factorial would overflow. You need to only divide if it's divisible.

          Link : here

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Actually I tried to check if (n-i+1)/i fails to be an integer... But failed.

            Maybe it stays an integer... I cant find any exception.

            Maybe putting that line prevents it somehow... I dont see how.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +22 Проголосовать: не нравится
              int ans=1;
                  for(int i=1;i<=r;i++){
                      ans=ans*(n-i+1)/i;
                  }
              

              This code is perfectly fine unless the answer exceeds the range of int. It works because product of r consecutive integer is always divisible by r!.

              so (ans*(n-i+1)) is divisble by i. and the expression is actually getting evaluated in order ans = (ans*(n-i+1))/i. so integer division is not a problem, unless ans exceeds the range of int.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится -11 Проголосовать: не нравится

                Try your code with n = 65536 and r = 2.

                The answer should be 2147450880, which fits within integer limit, but your code gives wrong output.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  Thats because ans*(n-i+1) is overflowing before getting divided by 2.

                  i think i wrote the word, its not the answer that exceeds int but variable ans that exceeds int.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can refer to editorial of this problem.