思路:动态规划
1.我们知道，一个数是3的倍数 等价于 它的数位和 是 3的倍数。也就是数位和%3=0
然后我们知道0~9里有
4个%3=0的数 , 分别是0,3,6,9
3个%3=1的数 , 分别是1,4,7
3个%3=2的数 , 分别是2,5,8
所以考虑动态规划:dp[i][j] 表示前i个数模3余j的方案数
P1940.2024.8.24&2024.9.20-oppo-第3题-小红的三子序列
题目内容
小红有一个长度为n的数字字符串s，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种可能的数字使得s是3的倍数（注意：s不含前导零）。
输入描述
第一行输入一个整数 n（1≤n≤105）代表数字字符串的长度。
第二行输入一个长度为n且仅由数字和′?′构成的字符串s。保证字符串不包含前导零。
输出描述
在一行上输出一个整数，代表满足是3的倍数的数字个数。由于答案可能很大，请将答案对（109+7）取模后输出
样例1
输入
4
12?4
输出
3
