JZTXT

小红过61

发布时间 2023-06-01 21:42:32作者: HeyStar

牛客2023年儿童节比赛

题目链接

题目描述

小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列，使得该子序列中不包含连续的"61"子串。
小红想知道，有多少种不同的子序列选择方式？答案对1e9+7取模。

输入描述:

一个仅由数字组成的字符串，长度不超过10^5

输出描述:

满足题目条件的子序列数量。

示例1

输入

12

输出

3

说明

有3个非空子序列，均符合条件。

示例2

输入

654321

输出

62

题意

在字符串str中找出不含"61"的子序列的个数

思路

一个字符也算是子序列，所以f的初始值为1，f用来表示目前能够构成的所有子序列的个数
sum用来表示含'6'的子序列的个数

代码

#include <iostream>

using namespace std;

const int MOD = 1e9+7;
const int N = 1e5+10;

int dp[N];

int main()
{
	string str;
	cin >> str;
	
	str = " " + str;
	
	int f = 1,sum = 0;
	for(int i = 1;i < str.length();i ++)
	{
		if(str[i] == '1') //如果出现字符1的话，需要将现有的所有的子序列的数量-含'6'的子序列的数量
			dp[i] = (f - sum + MOD)%MOD;
		else
			dp[i] = f;
		if(str[i] == '6')
			sum = (sum + dp[i]) % MOD;
		f = (f + dp[i]) % MOD;
	}
	
	int ans = 0;
	for(int i = 1;i < str.length();i ++)
	ans = (ans + dp[i]) % MOD;
	
	cout << ans << endl;
	
	return 0;
}