Skuteczny sposób na znalezienie liczbę kwot możliwych

Question

podawane trzy liczby całkowite n, k i d, ile sposobów można n być reprezentowany jako suma liczb całkowitych dodatnich i<=k, tak że d występuje przynajmniej raz w sumie. Jest oczywiste, że 0<d<=k. Moje podejście było rekurencyjne;

#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); 
} 

Wejście:
wyjściowa:
ale sędzia pokazuje Time Limit Exceeded. Czy istnieje jakikolwiek skuteczniejszy algorytm postępowania w tym przypadku? 0<n,k<=100 PS: Zastanawiam się, czy istnieje jakiś argument kombinatoryczny, który może rozwiązać to pytanie bez recursion lub iteration. I tak ... kolejność kwotsprawa.

Answer 1

Nawiązując do tej strony Wikipedia: Stars and Bars

Zasadniczo wiele sposobów podzielić liczbę n do k dodatnich liczb całkowitych jest (n-1)C(k-1) lub n-1 wybrać k-1. W ten sposób można iterować dla k = do n-d-1, aby znaleźć liczbę sposobów podziału n-d-1 na dowolną liczbę liczb całkowitych dodatnich.

Patrz here aby dowiedzieć się, jak skutecznie obliczyć nCk dla dużej n i k skutecznie

Answer 2

Można reprezentować swoje rekurencyjnych wywołań jako wykres. Każdy węzeł jest podany przez parametry twojej funkcji (totw, flag) i dodajesz krawędź za każdym razem, gdy wykonujesz wywołanie rekursywne. Na tym wykresie znajduje się około n*2 węzłów i n*2*k krawędzi.

Ten wykres ma bardzo interesującą właściwość: jest to DAG (np. Ponieważ totw wzrasta przy każdym wywołaniu). Dlatego, wywołując solve(totw, flag), możesz zachować wynik w tablicy, aby nie obliczać go dwukrotnie.

W ten sposób można wytłumaczyć dynamic programming: algorytm znajdowania najkrótszej ścieżki w DAG (z niewielkimi modyfikacjami może również obliczyć najdłuższą ścieżkę/liczbę ścieżek, ale masz pomysł). Złożoność czasu na wykresie G = (V, E) będzie wynosić O(|V|+|E|) (to w rzeczywistości rodzaj amortized analysis).

Dzięki temu przechowywanie wyników w tablicy spowoduje złożoność czasu w postaci O(nk).

Właściwie można sprawić, że realizacja nawet krócej, zmieniając nieznacznie wykresu:

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); 
} 

Nawiasem mówiąc nie umieścić flag powrotem do 0 po zwiększając ją.

Answer 3

Oczywiście niektóre kombinatoryki mogą rozwiązać ten problem, nawet bez użycia kodu. Ale rekurencyjne wyzwanie sprawiało przyjemność, gdy próbowałem kodować.

Lekko przetestowany przykład - niewiele bardziej wydajny niż OP.
(Etap 1, stosować więcej znaczące nazwy zmiennych)

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)); 
}