java - 通过删除总和不为 17 的连续数字对来计算删除的数字

Question

以下是我的问题陈述:
你得到的数字是以 10 为底的，你必须通过选择两个连续的数字并删除它们来完全删除它。但那2位数字之和不应该是17。我们将重复上述操作完全删除的数字称为 “好” .
例子:

9889 => 删除 88获取 99

99 => 删除 99彻底删除号码。
结论:9889是好 .
注意:我们无法删除 98或 89因为这两个数字的总和是 17 .

给定一个数 N(偶数)，你想找到 的数好 N 位数字取模 10^9 + 7 .也包括在计数中包含前导零的 N 位数字。
测试用例:
情况1:

Input: 2
Output: 98

案例2:

Input: 4
Output: 9926

案例3:

Input: 442
Output: 417551213

我尝试使用各种代码解决这个问题，但无法获得结果。

Answer 1

对于最后一个可能的坏状态的每个序列，必须有一个强制序列生成它。查看可能的通配符的位置(当然，提供选择的数字是感兴趣的数字)，并尝试找到一种模式。
在下面的例子中，为了对称，把 9s 换成 8s； x s 是通配符:
输入长度 4，错误结果 9898:

9898

输入长度 4，错误结果 98:

989x
98x8
9x98
x898

从上面的两个我们可以清楚地看到为什么我们会得到输出，9926个好的4位数字。
输入长度 6，错误结果 9898:

98989x
9898x8
989x98
98x898
9x9898
x89898

输入长度 6，错误结果 9898 OR 98:

9898xx
989xx8
98xx98
9xx898
xx9898

输入长度 6，错误结果 98:

989x9x
98x8x8
...
9x989x
...

等等。
python 代码:

# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
  if not 0<=k<=n: return 0
  b=1
  for t in range(min(k,n-k)):
    b*=n; b//=t+1; n-=1
  return b

def f(n):
  bads = 0
  
  for k in range((n - 2) // 2 + 1):
    bads += 9**k * binom(n, k)
  
  return (10**n - 2 * bads) % (10**9 + 7) 
  
print(f(442)) # 417551213