effiziente Art und Weise Anzahl von Summen zu finden möglich

Question

Gegeben drei ganzen Zahlen n, k und d, wie viele Arten kann n als Summe der positiven ganzen Zahlen dargestellt werden i<=k, so dass d mindestens einmal in der Summe auftritt. Es wird garantiert, dass 0<d<=k. Mein Ansatz war rekursiv;

#include <stdio.h> 
#include <stdlib.h> 
int n,k,d,ans=0; 
void solve(int totw,int flag)//totw is the total sum till now, and flag is to keep track of the number of d's in the sum. 
{ 
    if(totw>n) 
     return; 
    if(totw==n && flag>0)//flag>0--->at least 1 d 
    { 
     ans = (ans+1)%1000000007;//answer is expected modulo 10^9+7 
     return; 
    } 
    int i=1,h=k; 
    if(h>n-totw) 
     h=n-totw; 
    while(i<=h) 
    { 
     if(i==d) 
      flag++; 
     solve(totw+i,flag); 
     i++; 
    } 
} 
int main() 
{ 
    scanf("%d %d %d",&n,&k,&d); 
    solve(0,0); 
    printf("%d",ans); 
} 

Eingang:
Ausgang:
Aber der Richter zeigt Time Limit Exceeded. Gibt es in diesem Fall einen effizienteren Algorithmus? 0<n,k<=100
PS: Ich habe mich nur gefragt, ob es ein kombinatorisches Argument gibt, das diese Frage ohne oder iteration lösen kann. Und ja .... Reihenfolge der SummenAngelegenheit.

Answer 1

dieser Wikipedia-Seite Bezug: Stars and Bars

Grundsätzlich ist die Anzahl der Möglichkeiten, eine Zahl n in k positive ganze Zahlen zu teilen ist (n-1)C(k-1) oder n-1k-1 wählen. Daher können Sie für k = 1 bis n-d-1 iterieren, um die Anzahl der Möglichkeiten zu finden, wie Sie n-d-1 in eine beliebige Anzahl positiver Ganzzahlen aufteilen können.

Siehe here, um herauszufinden, wie effizient nCk

Answer 2

Sie für große n und k effizient Ihre rekursive Aufrufe als Diagramm darstellen zu berechnen. Jeder Knoten ist durch die Parameter Ihrer Funktion (totw, flag) gegeben, und Sie fügen eine Kante hinzu, wenn Sie einen rekursiven Aufruf durchführen. Es gibt ungefähr n*2 Knoten und n*2*k Kanten in diesem Diagramm.

Dieser Graph hat eine sehr interessante Eigenschaft: es ist ein DAG (z. B. weil totw bei jedem Aufruf streng zunimmt). Wenn Sie also solve(totw, flag) aufrufen, können Sie das Ergebnis in einem Array behalten, so dass Sie es nicht zweimal berechnen.

Dies ist eigentlich eine Erklärung dynamic programming: ein Algorithmus, um den kürzesten Pfad in einer DAG zu finden (mit leichten Modifikationen kann es auch den längsten Pfad/die Anzahl der Pfade berechnen, aber Sie bekommen die Idee). Die zeitliche Komplexität eines Graphen G = (V, E) ist ein O(|V|+|E|) (das ist eigentlich eine Art amortized analysis).

Wenn Sie also die Ergebnisse in einem Array halten, ergibt sich eine Zeitkomplexität von O(nk).

Eigentlich kann man die Umsetzung machen noch kürzer durch leicht die Grafik zu ändern:

enum { UNKNOWN = -1 }; 

/* not tested */ 
/* solve(num, d_seen): returns the answer to the problem with a sum 
    target, knowing whether `d` was already used */ 
int solve(int sum, int d_seen) 
{ 
    if (sum == 0) return d_seen; 
    int ans = dp[sum][d_seen]; 
    if (ans == UNKNOWN) { 
    ans = 0; 
    /* min(a, b) being what it is supposed to be */ 
    for (int i = 1; i <= min(sum, k); ++i) 
     ans = (ans + solve(sum - i, d_seen || (i == d))) % MOD; 
    } 

    return (dp[sum][d_seen] = ans); 
} 

Durch die Art und Weise Sie nicht nach dem Inkrementieren flag zurück auf 0 gesetzt haben.

Answer 3

Sicherlich kann eine kombinatorische Mathematik dies lösen, ohne Code zu verwenden. Aber die rekursive Herausforderung sah spaßig aus zu versuchen, zu codieren.

Ein leicht getestet, Beispiel - nicht viel effizienter als OPs.
(Schritt 1, aussagekräftigere Variablennamen)

unsigned long solve(unsigned sum_n, unsigned max_value_k, unsigned special_d) { 
    if (sum_n == 0) return special_d == 0; 
    unsigned long solutions = 0; 

    // Improve efficiency, only loop up to min(k,n) 
    if (max_value_k > sum_n) { 
    max_value_k = sum_n; 
    } 

    // Will the loop contain d? 
    if (max_value_k >= special_d) { 
    for (unsigned i = 1; i <= max_value_k; i++) { 
     solutions += solve(sum_n - i, max_value_k, 
      i == special_d ? 0 : special_d); 
     solutions %= 1000000007; 
    } 
    } 
    return solutions; 
} 

#include <stdio.h> 
int main(void) { 
    unsigned n, k, d; 
    for (n=0; n<100; n++) { 
    printf("%u %lu\n", n, solve(n, 100, 1)); 
    fflush(stdout); 
    } 
    scanf("%u %u %u", &n, &k, &d); 
    printf("%lu\n", solve(n, k, d)); 
}