string - 数字和可被 6 整除的子序列

Question

假设我有一个字符串，其字符不过是 [0 - 9] 范围内的数字。例如:“2486”。现在我想找出所有数字和可被 6 整除的子序列。例如:在“2486”中，子序列是 - “6”、“246”(2+ 4 + 6 = 12 可被 6 整除)， “486”(4 + 8 + 6 = 18 可被 6 整除)等。我知道生成所有 2^n 组合我们可以做到这一点。但这是非常昂贵的。最有效的方法是什么？

编辑:

我在 quora 的某个地方找到了以下解决方案。

int len,ar[MAXLEN],dp[MAXLEN][MAXN];

int fun(int idx,int m)

{

    if(idx==len)

        return (m==0);

    if(dp[idx][m]!=-1)

        return dp[idx][m];

    int ans=fun(idx+1,m);

    ans+=fun(idx+1,(m*10+ar[idx])%n);

    return dp[idx][m]=ans;

}

int main()

{

    // input len , n , array

    memset(dp,-1,sizeof(dp));

    printf("%d\n",fun(0,0));            

    return 0;

}

有人可以解释一下代码背后的逻辑是什么 - 'm*10+ar[idx])%n' 吗？为什么这里m乘以10？

Answer 1

假设您有一个 16 位数字的序列，您可以生成所有 2¹⁶ 个子序列并测试它们，即 65536 次操作。

或者您可以取前 8 位数字并生成 2⁸ 个可能的子序列，并根据它们的和模 6 的结果对它们进行排序，并对后 8 位数字执行相同的操作。这只是 512 次操作。

然后，您可以生成原始 16 位字符串的所有可被 6 整除的子序列，方法是将第一个列表的每个子序列的模值等于 0(包括空子序列)并将其与最后一个列表的每个子序列连接起来模值等于 0 的列表。

然后将第一个列表中模值等于 1 的每个子序列与最后一个列表中模值等于 5 的每个子序列连接起来。然后 2 与 4、3 与 3、4 与 2 和 5与 1.

因此，在 512 次操作的初始成本之后，您可以只生成总和可被 6 整除的那些子序列。您可以递归地应用此算法来处理更大的序列。