algorithm - 给定数组中可被 n 整除的子序列数

Question

我有一个数字序列，例如 1、2、4、0，我必须找到可被 6 整除的序列数。

所以我们将有 0,12,24,120,240，这意味着答案将为 5，

问题是我设计了一个算法，它需要 O(2^n) 时间复杂度，所以基本上它会遍历所有天真的可能性。

有什么方法可以降低复杂性。

Edit1:允许复制多个数字。例如输入可以是 1,2,1,4,3 Edit2:数字应该按顺序排列，例如上面的示例 42 420 等是不允许的

代码:然而，此代码无法考虑 120

`#include <stdio.h>
 #include<string.h>
 #define m 1000000007
 int main(void) {
 int t;
 scanf("%d",&t);
 while(t--)
 {
    char arr[100000];
    int r=0,count=0,i,j,k;
    scanf("%s",&arr);
    int a[100000];
    for(i=0;i<strlen(arr);i++)
    {
        a[i]=arr[i]-'0';
    }
    for(i=0;i<strlen(arr);i++)
    {
        for(j=i;j<strlen(arr);j++)
        {
            if(a[i]==0)
            {
                count++;
                goto label;
            }
            r=a[i]%6;
            for(k=j+1;k<strlen(arr);k++)
            {
                r=(r*10 + a[k])%6;
                if(r==0)
                count++;
            }
        }
        label:;
        r=0;
    }
    printf("%d\n",count);
 }
 return 0;
}

Answer 1

你可以使用动态规划。

像往常一样，当我们决定使用动态规划来解决问题时，我们首先将一些输入值转换为参数，然后可能会添加一些其他参数。

参数的明显候选者是序列的长度。 让我们的序列为 a[1], a[2], ..., a[N] . 因此，我们搜索值 f(n)(对于从 0 到 N 的 n)，它是a[1]、a[2]、...、a[n] 的子序列数当读作数字时，它可以被 D=6 整除。 当我们知道 f(n-1) 时计算 f(n) 看起来还不明显，所以我们深入研究细节。

仔细看，我们现在面临的问题是，在一个数的末尾加一个数字，可以把一个可以被D整除的数变成一个不能被D整除的数>，反之亦然。 不过，我们确切地知道当我们在数字末尾添加一个数字时余数如何变化。

如果我们有一个序列 p[1], p[2], ..., p[k] 并知道 r，余数 p[1] p[2] ... p[k] 模 D，然后将p[k+1]加入序列，新数p[1] p[2]的余数s ... p[k] p[k+1] modulo D 很容易计算:s = (r * 10 + p[k+1]) mod D.

考虑到这一点，我们可以将余数取模 D 作为我们的新参数。 所以，我们现在搜索 f(n,r)(对于 n 从 0 到 N 和 r from 0 to D-1) 是a[1]的子序列数，a [2], ..., a[n] 当读作数字时，余数 r 模 D.

现在，知道 f(n,0), f(n,1), ..., f( n,D-1)，我们要计算f(n+1,0), f(n+1,1), ...，f(n+1,D-1)。 对于 a[1]、a[2]、...、a[n] 的每个可能子序列>，当我们考虑元素编号 n+1 时，我们要么向其添加 a[n+1]，要么省略 a[n+1] 并保持子序列不变。 这比用公式更容易用正向动态规划来表达:

let f (n + 1, *) = 0
for r = 0, 1, ..., D - 1:
    add f (n, r) to f (n + 1, r * 10 + a[n + 1])  //   add a[n + 1]
    add f (n, r) to f (n + 1, r)                  //  omit a[n + 1]

结果 f (n + 1, s)(取决于 s，是一个或多个项的总和)是 a[1], a[2], ..., a[n], a [n+1] 产生余数 s 模 D。

整个解决方案如下:

let f (0, *) = 0
let f (0, 0) = 1  //  there is one empty sequence, and its remainder is 0
for n = 0, 1, ..., N - 1:
    let f (n + 1, *) = 0
    for r = 0, 1, ..., D - 1:
        add f (n, r) to f (n + 1, r * 10 + a[n + 1])  //   add a[n + 1]
        add f (n, r) to f (n + 1, r)                  //  omit a[n + 1]
answer = f (N, 0) - 1

我们从答案中减去一个，因为空子序列不被视为数字。

时间和内存要求是O (N * D)。 当我们注意到在每个给定时刻，我们只需要存储 f (n, *) 和 f 时，我们可以将内存降低到 O (D) (n + 1, *)，所以f的存储可以是2 * D而不是(N + 1) * D.

示例序列的插图:

-------------------------------
  a[n]           1   2   4   0
 f(n,r)  n   0   1   2   3   4
    r
-------------------------------
    0        1   1   2   3   6
    1        0   1   1   1   1
    2        0   0   1   2   4
    3        0   0   0   0   0
    4        0   0   0   2   5
    5        0   0   0   0   0
-------------------------------

练习:如何使用此解决方案去除带前导零的数字？ 我们需要另一个参数吗？