Berechnung Pow (a, nCr)% m effizient

Question

Ich denke, es gibt einige Verfahren zur Berechnung von pow (a, nCr)% b? Aber ich möchte wissen, wie ich dieses Problem in der Programmierung effizient lösen kann?

Answer 1

Ich kann eine Art denken, die nur ~O(n^2*log(m)) ist und erfordert nicht die Verwendung von großen Ganzzahlen. Ich habe eine Vorstellung von einem schnelleren (etwas wie O(k*log(m)*log(n))) Ansatz, wenn Sie Faktor m Faktor und totient (m/gcd(a^k,m)) für einige k Faktor, aber es wird ziemlich haarig.

Auf jedem Fall für den O(n^2*log(m)) Ansatz, werden wir von der Tatsache, dass nCr == (n-1) C (r-1) + (n-1) Cr

Hier ist eine Berechnung machen von nCr, die ausnutzt, dass:

def nCr(n0,r0): 
    memoized = {} 

    def go(n,r): 
    if r == 0 or r == n: 
     return 1 
    if (n,r) not in memoized: 
     memoized[(n,r)] = go(n-1,r-1) + go(n-1,r) 
    return memoized[(n,r)] 

    return go(n0,r0) 

der Code für Ihre powChooseMod Funktion wäre fast identisch sein:

def powChooseMod(a,n0,r0,m): 
    memoized = {} 

    def go(n,r): 
    if r == 0 or r == n: 
     return a 
    if (n,r) not in memoized: 
     memoized[(n,r)] = go(n-1,r-1) * go(n-1,r) % m 
    return memoized[(n,r)] 

    return go(n0,r0)