和为9的不连续子序列个数

有一个字符串，明明想取该字符串的子序列（子序列可以不连续），使得改子序列是9的倍数，子序列可以包括前导0，一共可以取多少个合法子序列，输出的字符串长度不超过200000，仅由‘0’-‘9’组成

第一种，和为9的倍数

9这个数字很特殊，为什么呢？

18 = 9+1+8  = 1+8 也是9的倍数，所以问题就转为为：找一串数字和为9的倍数的可不连续子序列

输入：

1 1 8 8 

输出

5

输入：

9 1 1 0 6 4 8 7 2 3 1 0 1

输出

879

 1 arr = list(map(int, input()))
 2 k = 9
 3 res =[]
 4 
 5 def find(i, pre):
 6     if i >= len(arr) :  return 
 7     pre += arr[i]
 8     if pre%k==0: 
 9         res.append(pre)
10     find(i+1, pre)
11     pre -= arr[i]
12     find(i+1, pre)
13 
14 pre = 0
15 vis = [0]*len(arr)
16 find(0, pre)
17 print(len(res))

还有一种写法就是

from copy import deepcopy
arr = list(map(int, input()))
k = 9
res =[]
ans = [0]*9

def find2():
    for num in arr:
        tmp = deepcopy(ans) #记录前一次状态
        ans[num%9] += 1 #每新加一个的数，更新下余数数组ans
        for i in range(9): #对于[0-8]
            ans[(num+i)%9] += tmp[i] #更新num加进来，each values of ans changes

find2()
print(ans[0])