Yếu tố không tiếp giáp chia hết cho n giải pháp không hoạt động

Question

Cách hiệu quả để đếm số lượng các chuỗi con không tiếp giáp của một dãy số nguyên có thể chia hết cho n là gì? A = {1,2,3,2} n = 6 Output vì 12, 12, 132 là chia hết cho 6

Giải pháp của tôi trong đó sử dụng lập trình động được đem lại cho tôi kết quả sai. Nó luôn mang lại cho tôi nhiều hơn kết quả thực tế.

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

Mọi người có thể chỉ ra sai lầm không?

Answer 1

Sự cố là chuỗi "trống" được coi là giải pháp (m == 0 khi bạn bắt đầu cuộc gọi và không thêm bất kỳ chữ số nào sẽ để bạn ở số m == 0 ở cuối).

Hoặc đó là chính xác nhưng sau đó giải pháp cho {1, 2, 3, 2} là 4 hoặc bạn cần phải trừ nó bằng cách chỉ trả lời fun(0, 0)-1.