链接:https://ac.nowcoder.com/acm/contest/58604/G 来源:牛客网 小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列,使得该子序列中不包含连续的"61"子串。 小红想知道,有多少种不同的子序列选择方式?答案对 1 0 9 + 7 10 9 +7取模。
时间: 2024-01-15 09:02:30 浏览: 65
我们可以使用动态规划来解决该问题。
设 $f_i$ 表示以第 $i$ 个字符结尾的、不包含连续的 "61" 子串的子序列个数。那么我们可以考虑第 $i$ 个字符的状态转移:
1. 如果第 $i$ 个字符不是 "6" 或 "1",那么它可以单独作为一个子序列,也可以加入到以第 $i-1$ 个字符结尾的子序列中。因此,状态转移方程为:
$$
f_i = (f_{i-1} + 1) \bmod 10^9 + 7
$$
2. 如果第 $i$ 个字符是 "6" 或 "1",那么它只能单独作为一个子序列,不能加入到以第 $i-1$ 个字符结尾的子序列中,因为这样会产生连续的 "61" 子串。因此,状态转移方程为:
$$
f_i = 1
$$
最终的答案即为 $f_1+f_2+\cdots+f_n$。
时间复杂度为 $O(n)$。
相关问题
https://ac.nowcoder.com/acm/contest/67743/L
很抱歉,我无法访问互联网上的链接。但是,我可以为您提供一些关于Nowcoder的一般信息。
Nowcoder是一个面向程序员的在线学习和竞赛平台,提供各种编程题目和算法竞赛。链接中的https://ac.nowcoder.com/acm/contest/67743/L可能是一个Nowcoder的竞赛链接,其中的"/acm/contest/67743/L"可能是竞赛的具体页面或题目链接。
如果您对Nowcoder平台或者竞赛有任何具体问题,我会尽力回答。请提出您的问题。
https://ac.nowcoder.com/acm/contest/61657/L
根据提供的引用内容,我无法回答你的问题。引用内容中包含了一些代码和链接,但没有提供具体的问题描述。请提供更详细的问题描述,我将尽力帮助你解答。
#### 引用[.reference_title]
- *1* *3* [2022/7/17/题解2022河南萌新联赛第(二)场:河南理工大学https://ac.nowcoder.com/acm/contest/37344](https://blog.csdn.net/m0_66433418/article/details/125835437)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [牛客·金币https://ac.nowcoder.com/acm/contest/19305/1021](https://blog.csdn.net/m0_66433418/article/details/125787020)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]