Brauche Hilfe in mod 1000000007 Fragen

Ich bin schwach in der Mathematik und bleibe immer mit den Problemen stecken, die eine Antwort erfordern.

zB: (500! / 20!) mod 1000000007

Ich bin mit BigIntegers vertraut, aber die Berechnung von Modulo nach der Berechnung des Faktors 500 (selbst nach der Verwendung von DP) scheint eine Menge Zeit zu beanspruchen.

Ich würde gerne wissen, ob es einen bestimmten Weg gibt, mit solchen Problemen umzugehen.

Hier ist ein solches Problem, das ich im Moment zu lösen versuche: http://www.codechef.com/FEB12/problems/WCOUNT

Es wäre wirklich hilfreich, wenn jemand mich zu einem Tutorial oder einem Ansatz leiten könnte, um mit diesen Codierungsproblemen umzugehen. Ich bin vertraut mit Java und C ++.

Der Schlüssel zu diesen Aufgaben mit großem Modul ist nicht die Berechnung des vollständigen Ergebnisses vor der Durchführung des Moduls. Sie sollten den Modul in den Zwischenschritten reduzieren, um die Zahl klein zu halten:

500! / 20! = 21 * 22 * 23 * ... * 500 21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200 4475671200 mod 1000000007 = 475671172 475671172 * 28 mod 1000000007 = 318792725 318792725 * 29 mod 1000000007 = 244988962 244988962 * 30 mod 1000000007 = 349668811 ... 31768431 * 500 mod 1000000007 = 884215395 500! / 20! mod 1000000007 = 884215395 

Sie müssen das Modul nicht bei jedem einzelnen Schritt reduzieren. Tun Sie es oft genug, um zu verhindern, dass die Zahl zu groß wird.


Beachten Sie, dass der maximale Wert von long 2 ^ 63 – 1 ist. Das Ausführen von 64-Bit-Multiplikationen zwischen zwei positiven ganzzahligen Werten (dh einer der Operanden ist long ) wird nicht long überlaufen. Sie können die Restoperation % anschließend sicher ausführen (wenn dies ebenfalls positiv ist) und bei Bedarf auf eine ganze Zahl zurückstellen.

Beginnen Sie mit der Beobachtung, dass 500!/20! ist das Produkt aller Zahlen von 21 bis 500, einschließlich und Weiter, beachten Sie, dass Sie Modulo Multiplikation Element für Element durchführen können, wobei %1000000007 am Ende jeder Operation. Sie sollten jetzt in der Lage sein, Ihr Programm zu schreiben. Achten Sie darauf, die Nummer nicht zu überschreiten: 32 Bit sind möglicherweise nicht genug.

Ich denke, das könnte für Sie von Nutzen sein

 for(mod=prime,res=1,i=20;i<501;i++) { res*=i; // an obvious step to be done if(res>mod) // check if the number exceeds mod res%=mod; // so as to avoid the modulo as it is costly operation }