题目内容

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

小欧字符串

题解思路

本题要求统计将字符串中问号替换为数字后，使得整个数字是3的倍数的方案数（注意替换后数字不含前导零）。

• 关键点：
  1. 一个数字是否是3的倍数，可以通过判断其各数位之和是否为3的倍数。
  2. 固定数字部分的和可以直接求出，再加上问号部分替换后所贡献的数位和。
  3. 对于问号的替换，采用数位DP思想：
     • 定义 dp[j] 表示经过若干个问号替换后，问号部分数位和模3为 j 的方案数。
     • 注意首位如果为问号，则只能替换成1到9（避免前导零）；其余位置允许填0~9。