01序列指的是01相间的序列,如“01010101010”,而“0110”不是。 求长度为n的01序列的子序列中有多少个也是01序列。(子序列的相邻字符在原串上可以不相邻) 由于这个数很大,请输出mod 1000000007后的值。
时间: 2024-02-17 10:01:46 浏览: 20
这是一个比较典型的动态规划问题。假设dp[i]表示以第i个字符结尾的01子序列的个数,那么显然有以下转移方程:
- 当s[i] = '0'时,dp[i] = dp[i-1]
- 当s[i] = '1'时,dp[i] = dp[i-1] + dp[j-1],其中j是最后一个字符为'0'的位置,满足j<i且s[j]='0'
初始状态为dp[0]=1,因为空串也是一个合法的01子序列。
最后,将所有的dp[i]累加起来就是长度为n的01子序列的个数。时间复杂度为O(n^2)。
下面是Python实现代码:
```python
MOD = 1000000007
def count_subsequences(n, s):
dp = [0] * (n + 1)
dp[0] = 1
last_zero = [-1] * 2 # 记录最后一个'0'出现的位置
for i in range(1, n + 1):
if s[i-1] == '0':
dp[i] = dp[i-1]
else:
dp[i] = dp[i-1] + dp[last_zero[(i-1)%2]]
dp[i] %= MOD
last_zero[i%2] = i-1 if s[i-1] == '0' else last_zero[(i-1)%2]
return sum(dp) % MOD
n = int(input())
s = input()
print(count_subsequences(n, s))
```