由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来减去它。