题目 https://www.dotcpp.com/oj/problem1117.html
参考 https://blog.dotcpp.com/a/75712
n位k进制数,无连续0,找有多少个这样的数
设:这个数为\(XXXXX(X表示还不确定)\)
设:\(_\)表示除0外的数\([1, k-1]\)
设:\(0\)表示0
那么解题的过程就转化为了确定\(X\)的过程
将确定\(X\)的过程用树表示出来
可以发现,每次确定\(X\)的时候都有两种情况,并且第二种情况会一次性确定两个\(X\)
那么解题思路就是:深搜确定\(X\),并在到达叶子节点时根据\(_\)的数量确定该分支能确定多少个数
n = int(input()) k = int(input()) s1 = 0 def dfs(depth, n_): global s1 if depth == n: s1 += pow(k-1, n_) return if depth == n + 1: s1 += pow(k - 1, n_ - 1) return for i in range(1, 2 + 1): dfs(depth + i, n_+1) dfs(1, 1) print(s1)