Nicht zusammenhängendes Element teilbar durch n Lösung funktioniert nicht

Question

Was ist ein effizienter Weg, um die Anzahl der nicht zusammenhängenden Untersequenzen eines gegebenen Arrays von ganzen Zahlen durch n teilbar zu zählen? A = {1,2,3,2} n = 6 Output weil 12, 12, 132 teilbar sind durch 6

Meine Lösung verwendet, die dynamische Programmierung mir gibt falsches Ergebnis. Es gibt mir immer mehr als das tatsächliche Ergebnis.

#include <stdio.h> 

#define MAXLEN 100 
#define MAXN 100 
int len = 1,ar[] = {1, 6, 2},dp[MAXLEN][MAXN],n=6; 

int fun(int idx,int m) 
{ 
    if (idx >= (sizeof(ar)/sizeof(ar[0]))) 
     return m == 0; 
    if(dp[idx][m]!=-1) 
     return dp[idx][m]; 
    int ans=fun(idx+1,m);    // skip this element in current sub-sequence 
    ans+=fun(idx+1,(m*10+ar[idx])%n); // Include this element. Find the new modulo by 'n' and pass it recursively 
    return dp[idx][m]=ans; 
} 
int main() 
{ 
    memset(dp, -1, sizeof(dp)); 
    printf("%d\n",fun(0, 0));   // initially we begin by considering array of length 1 i.e. upto index 0 
    return 0; 
} 

Kann jemand den Fehler aufzeigen?

Answer 1

Das Problem ist, dass die "leere" Sequenz als eine Lösung betrachtet wird (m == 0, wenn Sie den Anruf starten und keine Ziffer hinzufügen wird Sie mit m == 0 am Ende verlassen).

Entweder das ist richtig, aber dann ist die Lösung für {1, 2, 3, 2} 4, oder Sie müssen es subtrahieren, indem Sie einfach als Antwort geben fun(0, 0)-1.