解题思路
问题分析
我们需要统计字符串 t 的所有非空子序列，满足以下两点才算有效：
- 无前导零：除单个字符
"0" 以外，不允许以 '0' 开头。
- 数字和可被 5 整除。
对每个有效子序列，根据其首位和末位数字分别给分：
P2882.第2题-数字之宴
题目内容
现给定一个仅由数字 0,1,2,...,9构成的字符串t，系统将基于t的所有非空子序列计算奖励分数。
一个子序列被认为是有效的必须同时满足以下条件：
1、子序列所表示的整数不得包含前导零(例如01、007均不合法)，但单个字符0被视为合
法:
2.子序列中所有数字之和须能被5整除，即∑digit∈子序列 digit=0(mod 0)
对于每个有效子序列，系统根据以下规则给予奖励:
- 若有效子序列的首位数字属于{2,3,5,7}(即素数数字)且末位数字为偶数，则奖励分数为4分;
- 若有效子序列的首位数字属干{2,3,5,7}
- 其余有效子序列奖励1分。
请计算字符串t的所有非空有效子序列的累计奖励分数，并输出结果对(109+7)取模后的值。
【名词解释】
- 子序列:子序列为从原字符串中删除任意个(可以为零或全部)字符得到的新字符串，字符的
相对顺序保持不变。
- 前导零:前导零指数字字符串最前面的多余零，例如"01"中的0被视为前导零；但单独的"0" 被视为合法。
- 素数数字: 指2、3、5、7四个数字，它们均为质数。
注意，子序列在选取时必须保持原字符串中字符的顺序不变。
输入描述
输入一个仅由数字0,1,2,...,9组成的字符串t，其中字符串长度满足(1≦∣t∣≤105)
输出描述
输出一个整数，表示字符串t的所有非空有效子序列的累计奖励分数对(109+7)取模后的结果。
样例1
输入
248
输出
4
说明
对于这组样例:
-
字符串“248"的所有非空子序列为:
-
"2": 数字和为2，不满足2=0(mod 5);
-
"4": 数字和为4;
-
"8": 数字和为8;
-
"24": 数字和为2+4=6;
-
"28": 数字和为2+8=10，满足条件;
-
"48": 数字和为4+8=12;
-
"248": 数字和为2+4+8=14;
其中，只有“28”为有效子序列，其首位数字为2(属于{2,3,5,7})，末位数字为8(偶数)，因此奖励4分。
样例2
输入
205
输出
4
说明
对于这组样例:
- 字符串“205”的非空子序列包括:
-
"0": 合法(单个零)，数字和为0满足条件，奖励 1分;
-
"5": 数字和为5，其首位为’5’(属于 {2,3,5,7})，末位为’5’(奇数)，奖励3分;其他子序列因前导零或数字和不满足条件而无效。
累计奖励分数为1+3=4分。
