链接：https://ac.nowcoder.com/acm/contest/78807/D
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Bingbong 有一个长度为 n 的数字字符串 S，该字符串仅包含 [0, 9] 的数字。
Bingbong 想要从中挑选出若干个字符，然后按照其相对顺序重新拼接而成一个数字，使其是一个无前导 0 的偶数。
例如：当 n = 3, S = 100。其包含的偶数数字有 0, 0, 10, 10, 100。而 00 是不符合条件的，因为其含有前导 0。
由于字符串实在是太长了，他一个人数不过来，请您帮他计算一下该字符串中含有的偶数方案总数， 结果对 1e9 + 7 取模。
输入描述:
第一行一个整数 n (1 ≤ n ≤ 2×10^5)，表示字符串 S 的长度。
第二行一个长度为 n 的字符串 S ，保证输入只含 [0, 9] 的数字。
输出描述:
一个整数，表示最后含有的偶数方案总数。
示例1
输入
3
100
输出
5
示例2
输入
5
12345
输出
10
解答
- 此题使用
dp的思想，记录之前所有的方案，然后看要加入的数能否构成答案，如果可以就加入答案，并计算这个数能构成的方案 ans表示的是从它往前的偶数集合pre表示的是当前数前面的数，能构成哪些数的集合，这就不管偶数还是奇数了，表示一个集合- 很抽象，对吧
- 假设
1024，遍历到2的时候，pre表示的是：10，1，0，解释ans = ans + pre + 1，pre要加是因为pre是一个集合，这个集合内的数加上当前数一定是偶数，ans是前面合法情况，+1是加上当前数单独作为一种情况 - 解释为啥
s[i -1] != '0'，要pre++，原因是当前数的前者数是偶数，需要把这个数加入pre，而加入后组成的数，前面pre可选，可不选，当前数可选可不选，后面也就是(pre + 1) * 2种方案也就满足，而等于0情况，也就是当前0一定不选，前面pre可选可不选，直接pre * 2，所以不等于加1，然后再×2，另一个直接x2
#include <iostream>
#include <string>
using namespace std;
const int mod = 1e9 + 7;
int n;
string s;
int main()
{
cin >> n >> s;
long long ans = 0, pre = 0;
for (int i = 0; i < n; i++)
{
if (i > 0 && s[i - 1] != '0') pre++;
if (s[i] % 2 == 0) ans = (ans + pre + 1) % mod;
pre = (pre * 2) % mod;
}
cout << ans << endl;
return 0;
}