定数组是整除n个子序列号数组、序列号、个子
我有一个数字序列说1,2,4,0，我必须找到序列整除的数6。
因此，我们将有0,12,24,120,240这意味着答案是5，
现在的问题是，我设计了一个算法，需要 O（2 ^ n）的时间复杂度所以基本上通过所有这些天真的可能性迭代。
有没有一些方法来降低复杂性。
EDIT1：数字的多个拷贝是允许的。例如输入可以是1,2,1,4,3 EDIT2：数字应该是为了例如在上面的例子中42 420等都是不允许的。
code：然而，这code不是能够采取120到
`的#include＆LT; stdio.h中＆GT;
＃包括＆LT; string.h中＆GT;
＃定义米1000000007
诠释的主要（无效）{
INT吨;
scanf函数（％d个，＆amp; T公司）;
而（T--）
{
焦炭ARR [100000]。
INT R = 0，计数= 0，I，J，K;
scanf函数（％S，与放大器; ARR）;
诠释一个[100000]。
对于（i = 0; I＆LT; strlen的（ARR）;我++）
{
A [1] =改编[Ⅰ] - '0';
}
对于（i = 0; I＆LT; strlen的（ARR）;我++）
{
为（J =; J＆LT; strlen的（ARR）; J ++）
{
如果（A [1] == 0）
{
算上++;
转到标号;
}
R = A [1]％6;
对于（K = J + 1; K＆LT; strlen的（ARR）; k ++）
{
R =（R * 10 + A [K]）6％;
如果（R == 0）
算上++;
}
}
标签：;
使r = 0;
}
的printf（％D \ N，算）;
}
返回0;
}
解决方案
您可以使用动态规划。
像往常一样，当我们决定使用动态规划来解决一个问题，我们首先会将某些输入值到参数，也许加入一些其他参数。
有一个参数的明显的候选是序列的长度。
让我们的序列是 A [1] ， A [2] ， ... ， A [N] 。
因此，我们搜索的值 F（N）（对于 N 从 0 到 N ），这是 A [1] ， A [2] ， ... ， A [N] 其中，当读出的数字，是由整除D = 6 。
计算 F（N）当我们知道 F（N-1）看起来不很明显的是，让我们深入详细信息。
在仔细看看，我们现在面临的问题是，添加一个数字，数字的结束可以把数整除 D 成数不 D ，反之亦然。
然而，我们知道，当我们添加一个数字到数字的结束，其余究竟是如何发生变化。
如果我们有一个序列 P [1] ， P [2] ， ... ， P [K] ，知道研究时，剩余的号码 P [1] P [2] ... P [K] 模 D ，然后添加 P [K + 1] 的序列，其余的S 新号码 P [1] P [2] ... P [K] P [K + 1] 模 D 容易计算： S =（R * 10 + P [K + 1]）MODð。
要考虑到这一点，我们可以做其余模 D 我们的新参数。
所以，我们现在搜索 F（N，R）（对于 N 从 0 到 N 和研究从 0 到 D-1 ），这是子序列的数 A [1] ， A [2] ， ... ， A [N] 其中，读取时数字，有剩余研究模 D 。
现在，知道 F（N，0）， F（N，1）， ... ， F（N，D-1），我们要计算 F（N + 1 ，0）， F（N + 1,1）， ... ， F（N + 1，D-1）。
对于的每一个可能的子序列[1] ， A [2] ， ... ， A [N] ，当我们考虑的元素数量 N + 1 ，我们要么添加 A [N + 1] 来，或者省略 A [N + 1] 并保留序列不变。
这是通过前向动态规划，而不是一个公式更容易EX preSS：
让F（N + 1，*）= 0
当r = 0，1，...，D - 1：
添加F（N，r）的至f（n + 1个，R * 10 + A [N + 1]）//添加[N + 1]
添加F（N，r）的至f（n + 1个，r）的//省略[N + 1]
生成的 F（N + 1，S）（其中，因取值，是一笔一个或多个方面）是 A [1] ， A [2] ， ... ， A [N] ， A [N + 1] 而产生的余数取值模 D 。
整体解决方案如下：
让F（0，*）= 0
令f（0，0）= 1 //，有一个空的序列，和其余数为0
对于n = 0，1，...，N - 1：
令f（n + 1个，*）= 0
当r = 0，1，...，D - 1：
添加F（N，r）的至f（n + 1个，R * 10 + A [N + 1]）//添加[N + 1]
添加F（N，r）的至f（n + 1个，r）的//省略[N + 1]
答案= F（N，0） - 1
我们从应答减去之一，因为空子序列不被认为是一个数。
的时间和内存要求 O（N * D）。
我们可以降低内存 O（D）时，我们注意到，在每一个特定的时刻，我们只需要存储 F（N，*） 和 F（N + 1，*），所以存储 F 可 2 * D 而不是（N + 1）* D 。
与你的榜样序列的说明：
-------------------------------
A [N] 1 2 4 0
F（N，R）N 0 1 2 3 4
ř
-------------------------------
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
-------------------------------
练习：如何获得带有前导零与此解决方案消除数字？ 我们需要另一个参数？
I have a sequence of numbers say 1,2,4,0 and I have to find number of sequence divisible by 6.
So we will have 0,12,24,120,240 which means answer will be 5,
The problem is that I devised an algorithm which requires O(2^n) time complexity so basically it iterates through all the possibilities which is naive.
Is there some way to decrease the complexity.
Edit1: multiple copy of digit is allowed. for example input can be 1,2,1,4,3 Edit2: digits should be in order such as in above example 42 420 etc are not allowed
code: This code however is not able to take 120 into account
`#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;
}
解决方案
You can use dynamic programming.
As usual, when we decide to solve a problem using dynamic programming, we start by turning some input values into parameters, and maybe adding some other parameters.
The obvious candidate for a parameter is the length of the sequence.
Let our sequence be a[1], a[2], ..., a[N].
So, we search for the value f(n) (for n from 0 to N) which is the number of subsequences of a[1], a[2], ..., a[n] which, when read as numbers, are divisible by D=6.
Computing f(n) when we know f(n-1) does not look obvious yet, so we dig into details.
On closer look, the problem we now face is that adding a digit to the end of a number can turn a number divisible by D into a number not divisible by D, and vice versa.
Still, we know exactly how the remainder changes when we add a digit to the end of a number.
If we have a sequence p[1], p[2], ..., p[k] and know r, the remainder of the number p[1] p[2] ... p[k] modulo D, and then add p[k+1] to the sequence, the remainder s of the new number p[1] p[2] ... p[k] p[k+1] modulo D is easy to compute: s = (r * 10 + p[k+1]) mod D.
To take that into account, we can make the remainder modulo D our new parameter.
So, we now search for f(n,r) (for n from 0 to N and r from 0 to D-1) which is the number of subsequences of a[1], a[2], ..., a[n] which, when read as numbers, have the remainder r modulo D.
Now, knowing f(n,0), f(n,1), ..., f(n,D-1), we want to compute f(n+1,0), f(n+1,1), ..., f(n+1,D-1).
For each possible subsequence of a[1], a[2], ..., a[n], when we consider element number n+1, we either add a[n+1] to it, or omit a[n+1] and leave the subsequence unchanged.
This is easier to express by forward dynamic programming rather than a formula:
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]
The resulting f (n + 1, s) (which, depending on s, is a sum of one or more terms) is the number of subsequences of a[1], a[2], ..., a[n], a[n+1] which yield the remainder s modulo D.
The whole solution follows:
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
We subtract one from the answer since an empty subsequence is not considered a number.
The time and memory requirements are O (N * D).
We can lower the memory to O (D) when we note that, at each given moment, we only need to store f (n, *) and f (n + 1, *), so the storage for f can be 2 * D instead of (N + 1) * D.
An illustration with your example sequence:
-------------------------------
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
-------------------------------
Exercise: how to get rid of numbers with leading zeroes with this solution? Will we need another parameter?
