题目内容

小塔有一个长度为$n$的数字字符串$s$，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种可能的数字使得$s$是3的倍数（注意：$s$不含前导零）。

思路:动态规划

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的方案数 转移方程: $dp[i][(j+a[i])\mod 3] += dp[i-1][j]$ , 其中a[i]表示第i个数，如果a[i]是问号，那么a[i]可以取0~9，如果a[i]不是问号，那么a[i]只能取a[i]。