Bingbong的奇偶世界

标签： 字符串 动态规划，dp

难度： 较难

思路：

因为前导不为0，还要求为偶数，那只需限制第一个数不为0，末尾的数为偶数。

可以设置一个dp[][3]数组，dp[i][1] 用于记录前i个数，形式为[1-9]xxx 子序列的个数；

dp[i][2] 用于记录前i个数，形式为[1-9]xxx[02468]子序列的个数。

处理时，发现一位的时候，第一位和最后一位重合，需特判，不然麻烦。 两位以上时：

• 首先，继承上一位状态 dp[i][j]=dp[i-1][j]。

• 其次，当前状态加上上一位状态。

• 然后，第i位如果是偶数，dp[i][2]就能更新,dp[i][2]+=dp[i-1][1]。

• 最后，判断首位，若果不为0，就能做首位，当前dp[i][1]++。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

ll n,dp[200010][3];
//dp[i][1]: 前i个数，形式为  [1-9]xxx 子序列个数
//dp[i][2]: 前i个数，形式为  [1-9]xxx[02468]  子序列个数
char s[200010];


void add(ll &x,ll y)
{
	x+=y;
	if(x>=mod)
		x-=mod;
}

int main()
{
	cin>>n>>&s[1];
	
	ll ans=0;
	
	//特判一位数
	for(int i=1;i<=n;i++)
		if((s[i]-'0')%2==0)ans++;
	
	for(int i=1;i<=n;i++)
	{
		//首先，继承前一位状态
		for(int j=1;j<=2;j++)
			dp[i][j]=dp[i-1][j];
	
		add(dp[i][1],dp[i-1][1]);
		
		//第i位如果是偶数，dp[i][2]就能更新
		if((s[i]-'0')%2==0)
		{
			add(dp[i][2],dp[i-1][1]);
		}
		
		//判断首位，如果不是0，就能做首位,dp[i][1]++
		if(s[i]!='0')
			add(dp[i][1],1ll);
		
	}
	
	add(ans,dp[n][2]);
	cout<<ans<<endl;
	
	
	return 0;
}

补充：

3ll为将3强制类型转换为long long 类型。