计算生成没有连续K个零的字符串的方法数

Question

计算生成没有连续K个零的字符串的方法数

algorithm

4

给定一个长度为N的字符串，只由0和1组成。但是某些位置上是“？”。这意味着我们可以在那里放置0或1。

现在的问题是，我们需要计算填充这些“？”位置的方法数，使得不能有K个0放在一起。

比如说，我们有长度为N=4的字符串，字符串为0??0。

假设K=3，则在这里我们只能在两个位置中的最多一个位置上放置“0”。因此，字符串为:

0100
0010
0110

所以答案是3。现在我们需要计算长度为N和K的给定字符串的制作方法数量。

我的方法是使用动态规划来解决这个问题，具有O(N,K)的时间复杂度。如果我们在第i个位置放置0，则可以在下一个连续的“？”段中放置K-1个零，如果我们放置1，则可以再次放置K个零。

但是N和K可能非常大，因此是否有更好、更有效的算法？

代码如下：

int n,k;
cin>>n>>k;
string s;
cin>>s;
s="#"+s;
int size=s.length();

vector<long long int>F(size+1);
F[0]=1;
for(int i=1;i<=size;i++){
    if(s[i]=='R')
    {
        F[i]=0;
    }       
    else if(s[i]=='L'){
        F[i]=1;
    }
    else{
        for(int j=i-1;j>=i-k;j--){
            if(j<0)
            break;
            F[i]=(F[i]+F[j])%MOD;
        }
    }
}
cout<<F[size]<<"\n";

现在它在一个比较大的测试用例中失败了。但我使用暴力解决方案运行它，结果并不匹配。

测试用例：n=73，k=7，字符串s=???L?R?LLL?L?L?L?LLL???L???RL?????LR?L?LLRL??R???L?RL????RL?R??LL??LLLR?R

答案应该是877905026。但是代码给出的是246470268。

- user119249

N和K有多大？ - Peter de Rivaz

@PeterdeRivaz 2 <= K <= N <= 1,000,000。我知道答案可能非常大，因此我需要对某个质数M（比如1000000007）取模。 - user119249

有没有关于 ? 数量的限制？ - Pham Trung

@PhamTrung 不，没有这样的限制。 - user119249

似乎是欧拉计划的问题？ - dfens

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

提示

您可以使用数组F[n]来计算填充位置[0，n）的方法数，使得没有连续的K个0并且在位置n-1上有一个1。

然后，为了基于先前的结果计算F[n+1]，我们知道在位置n上有一个1，在之前的0和K-1之间有零。让0的数量为k。

F[0] = 1
F[n] = sum F[n-1-k] for k in 0,1,..,K-1 
   (only including values for k up to where the string at n-1-k is forced to be 1)

这应该可以给出正确答案，但会花费O(NK)的时间。

然而，我们可以通过维护值为F[n]的前缀和来加速求和的计算。换句话说，如果我们存储一个数组S[n]=F[0]+F[1]+F[2]+...+F[n]，我们可以通过减去两个S[n]的值快速计算F的特定索引上的求和。

因此，通过跟踪强制1的最后位置，您可以在O(N)的时间内计算出复发。

最终的答案将由F[N+1]给出。

例1：

对于K=3和一个0??0的字符串的示例：

F[0] = 1  (Just the empty string)
F[1] = 0 : position n-1=0 is forced to be 0 so no solutions are possible
F[2] = F[1]+F[0] = 1  (Just the string 01)
F[3] = F[2]+F[1]+F[0] = 2 (The strings 001 and 011)
F[4] = 0 : position n-1=3 is forced to be 0 so no solutions possible
F[5] = F[4]+F[3]+F[2] = 3  (the strings 0010 and 0110 and 0000)

最终答案是3。

例子2

对于第二个例子10???0??

F[0] = 1 (empty string)
F[1] = 1 (The string 1)
F[2] = 0
F[3] = F[2]+F[1] = 1 (The string 101)
F[4] = F[3]+F[2]+F[1] = 2 (The strings 1011 and 1001)
F[5] = F[4]+F[3]+F[2] = 3 (10011 and 10111 and 10001)
F[6] = 0
F[7] = F[6]+F[5]+F[4] = 5 (1011001, 1001001, 1001101, 1011101, 1000101)
F[8] = F[7]+F[6]+F[5] = 8 (10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, and 10001001)
F[9] = F[8]+F[7]+F[6] = 13
           10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, 10001001
           10110010, 10010010, 10011010, 10111010, 10001010

代码修复

你的代码几乎正确：将内部循环更改为以下内容后，它会给出你想要的答案：

if(s[i]=='R')
{
    F[i]=0;
} else{
    for(int j=i-1;j>=i-k;j--){
        if(j<0)
            break;
        F[i]=(F[i]+F[j])%MOD;
        if (s[j]=='L')
            break;
    }
}