由n解決方案不能工作的非連續元素

Question

什麼是一個有效的方法來計算一個給定的整數的非連續的子序列數可以被n整除？ A = {1,2,3,2} N = 6 輸出因爲12，12，132是整除6

我的解決方案，它使用動態編程是給我錯誤的結果。它總是給我一個比實際結果更多的東西。

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

任何人都可以指出錯誤嗎？

Answer 1

問題是，「空」序列被認爲是一個解決方案（m == 0當你開始通話，並沒有添加任何數字將在末尾離開你m == 0）。

要麼這是正確的，但然後{1, 2, 3, 2}的解決方案是4，或者您需要通過僅給出答覆fun(0, 0)-1來減去它。