牛客34442J - 收集者

• 链接：https://ac.nowcoder.com/acm/contest/34442/J
• 知识点：计数DP,组合数学
• 难度：紫

题意

• 给出一个长度为 $nn$ 的 01串，你需要从中选出一个开头为 $11$ 的子序列
• 能选出多少种长得不一样的子序列。
• （题目额外要求：如果给出的01串中有0，最后的答案额外加1。）

思路

错误思路：利用组合数公式

• 错误原因：去重太麻烦。

正确思路：DP

• $dp[i]dp[i]$ 代表截止到第 $ii$ 位（第 $ii$ 位可选可不选），有多少种子序列。
• 对于每一位，有选和不选两种选择。
• 如何去重？
• 以下面的01串举例：
• $100011100011$

假设第 $curcur$ 位是 $00$，在它之前上一位是 $00$ 的位置是 $prepre$，

• 那么第$pre-1pre-1$的dp结果，经由pre和cur会出现这种情况：
  • 第pre位给某个子序列追加了0，而第cur位没有给它追加0
  • 第pre位没有给某个子序列追加了0，而第cur位给它追加了0
• 某一个子序列经由这两种情况，最后的长相是一样的，应该去掉其中一个。
• 总共应该去掉几个呢？
• 去掉 $dp[pre-1]dp[pre-1]$ 个。

假设第 $curcur$ 位是 $11$，在它之前上一位是 $11$ 的位置是 $prepre$，

• 跟上面的一样。会出现第pre位给某个子序列追加了1，而第cur位没有给它追加1；和第pre位没有给某个子序列追加了 1，而第cur位给它追加了 1 的情况。
• 注意看 $i=6i=6$ 的情况，重复的元素的元素数量，就等于 $dp[pre-1]dp[pre-1]$，因为“1，10，100，1000”在经由 i=5 和 i=6 时，出现了只有一次加上了 1 的情况。

大概是全网最详细的解析了叭，确定不点个赞再走嘛？

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
const int N	= 1e6+10;
const int MOD	= 1e9+7;
using namespace std;

char str[N];
int dp[N],pre[2];
bool have0=false;
int n;

void Solve()
{
	int st=0;
	while (str[st]!='1')
		st++;
	
	dp[st]=1;
	for (int i=st+1; i<=n; i++)
	{
		dp[i] = dp[i-1] * 2 % MOD  - (pre[str[i]-'0']>0)*(dp[ pre[ str[i]-'0' ]-1 ]);
		dp[i] += MOD, dp[i]%=MOD;
		pre[ str[i]-'0' ] = i;
	}
	printf("%lld\n",(dp[n]+have0)%MOD);
}

signed main()
{
	scanf("%s",str+1);
	n=strlen(str+1);
	
	for (int i=1; i<=n; i++)
	{
		have0 |= (str[i]=='0');
	}
	Solve();
	
	return 0;
}