#P12607. 三叉求和
三叉求和
题目背景
很久很久以前,小 A 在一棵无穷深的三叉树上摘苹果,这棵苹果树的根没有苹果,每个点三个儿子的苹果的数量分别是这个点的苹果数量的三倍加上 ,小 A 从根节点一直往下走了正好 步并摘到了 个苹果,可惜的是,小 A 只记得 在三进制下的某些位,他想知道有多少种方式符合他的记忆。
题目描述
有一棵深度无穷大的以 为根的三叉树,节点 的儿子分别是节点 。
设节点 的点权为 。对于 ,有 ,特别的,。
你的任务是求从根出发,找长度 的简单路径,并使得该路径经过的所有点的点权和为 。你需要求出所有合法路径的条数。
然而 并不唯一, 的三进制表示中仅有某些位是已知的,而其它的位将以字符 表示。你需要对所有可能的 在上述问题中的答案求和,最后再对 取模。
输入格式
第一行一个整数 。
第二行一个长度为 的字符串,表示三进制形式的 。注意 可能有前导零。
输出格式
输出一行一个整数,表示你所求的答案。
3
?12
3
3
???
19
4
0211
1
10
21??1?2??0
161
30
???1????0????1???0????2???????
744432249
提示
样例 #1 解释
合法的路径有:
对应的点权分别为:
数据范围
测试点编号 | 特殊性质 | |
---|---|---|
- | ||
A | ||
B | ||
- | ||
A | ||
B | ||
- | ||
A | ||
B | ||
- |
特殊性质 A:保证 中 的数量 。
特殊性质 B:保证所有的位置均为 。
对于 的数据,。