java - Calculate C(n, k) combinations for big numbers using modInverse -


i want calculate combinations c(n, k) n , k large. tried using modular inverse following, it's not giving correct output small numbers. can tell me i'm wrong?

import java.math.biginteger;  public class test {      public static int[] factorials = new int[100001];     public static int mod = 1000000007;     public static biginteger mod = biginteger.valueof(1000000007);      public static void calculatefactorials() {          long f = 1;          (int = 1; < factorials.length; i++) {             f = (f * i) % mod;             factorials[i] = (int) f;         }      }      // choose(n, k) = n! / (k! * (n-k)!)     public static long nck(int n, int k) {          if (n < k) {             return 0;         }          long = biginteger.valueof(k).modinverse(mod).longvalue();         long b = biginteger.valueof(n - k).modinverse(mod).longvalue();          // left right associativity between * , %         return factorials[n] * % mod * b % mod;      }      public static void main(string[] args) {          calculatefactorials();         system.out.println(nck(5, 2));      }  }

the lines

    long = biginteger.valueof(k).modinverse(mod).longvalue();     long b = biginteger.valueof(n - k).modinverse(mod).longvalue();

should be

    long = biginteger.valueof(factorials[k]).modinverse(mod).longvalue();     long b = biginteger.valueof(factorials[n - k]).modinverse(mod).longvalue();

you might consider caching inverse factorials factorials.


Comments

Post a Comment

Popular posts from this blog

javascript - Jquery show_hide, what to add in order to make the page scroll to the bottom of the hidden field once button is clicked -

i have button on website when clicked, reveals map. button can seen when page first loads up, when clicked, section holding map slides open , goes out of screen since page loads @ top (normal). want page scroll down bottom of div select when button pushed, if map out of screen. if page scrolled down, , clicks show map button, don't want page jump bottom of map. i tried figure out myself, no luck. seasoned jquery coders able give me guidance? many thanks! map = mapdiv.gmap3("get"); infobox = new infobox({ pixeloffset: new google.maps.size(-220, -310), closeboxurl: '', enableeventpropagation: true }); mapdiv.delegate('.infobox .close','click',function () { infobox.close(); }); jquery(".slidingdiv").hide(); jquery(".show_hide").show(); jquery('.show_hide').click(function(){ lastcenter=map.getcenter(); jquery(".slidingdiv&quo
Read more

javascript - Highcharts multi-color line -

Image
i looking create highchart multi-colored line. if goes down under value, become red, , when comes on value, become green . here picture example: or maybe highcharts have other charts models differentiate high or low level color? you can achieve coloring using lineargradient coloring: color: { lineargradient: { x1: 0, x2: 0, y1: 0, y2: 1 }, stops: [ [0, 'red'], [0.25, 'yellow'], [0.50, 'green'], [0.75, 'yellow'], [1, 'red'] ] } here 0 in stops relates minimum value of series , 1 maximum value, , in between percentages between values. if find percentages according values prior creating chart use correct stops values make relate specific values in data (at least approximately). see this jsfiddle example .
Read more

javascript - Enter key does not work in search box -

tried search guys sorry. input in search box doesnt work (or search) when hit enter when user clicks search button. doing wrong? here code. thanks. <script type="text/javascript"> $(document).ready(function() { $("#submit").click(function() { var url = "http://asla.org/awardssearch.html"; url += "?s=" + $('#googlecse').val(); window.location = url; }); $('#googlecse').keydown(function(event) { if (event.keycode == '13') { $("#submit").click(); } else { //do nothing :) } }); }); </script> <form class="navbar-form navbar-right" role="search"> <div class="search"> <input id="googlecse" type="text" onblur="if(this.value=='')this.value=this.defaultvalue;" onfocus="if(this.value==this.defaultvalue)t
Read more