303926: CF756E. Byteland coins
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Byteland coins
题意翻译
你现在有 $n$ 种金币,第 $i$ 种金币的面额是 $\prod_{j=1}^{i-1} a_j$,有 $b_i$ 枚。保证对于一个相同的 $x$,面值为 $x$ 的金币不会超过 $20$ 种。 求凑出总面值为 $m$ 的方案数,模 $10^9+7$。 $m \leq 10^{10000}$,$n, \sum b_i \leq 3\times 10^5$,$1\leq a \leq 10^9$。题目描述
There are $ n $ types of coins in Byteland. Conveniently, the denomination of the coin type $ k $ divides the denomination of the coin type $ k+1 $ , the denomination of the coin type $ 1 $ equals $ 1 $ tugrick. The ratio of the denominations of coin types $ k+1 $ and $ k $ equals $ a_{k} $ . It is known that for each $ x $ there are at most 20 coin types of denomination $ x $ . Byteasar has $ b_{k} $ coins of type $ k $ with him, and he needs to pay exactly $ m $ tugricks. It is known that Byteasar never has more than $ 3·10^{5} $ coins with him. Byteasar want to know how many ways there are to pay exactly $ m $ tugricks. Two ways are different if there is an integer $ k $ such that the amount of coins of type $ k $ differs in these two ways. As all Byteland citizens, Byteasar wants to know the number of ways modulo $ 10^{9}+7 $ .输入输出格式
输入格式
The first line contains single integer $ n $ ( $ 1<=n<=3·10^{5} $ ) — the number of coin types. The second line contains $ n-1 $ integers $ a_{1} $ , $ a_{2} $ , $ ... $ , $ a_{n-1} $ ( $ 1<=a_{k}<=10^{9} $ ) — the ratios between the coin types denominations. It is guaranteed that for each $ x $ there are at most 20 coin types of denomination $ x $ . The third line contains $ n $ non-negative integers $ b_{1} $ , $ b_{2} $ , $ ... $ , $ b_{n} $ — the number of coins of each type Byteasar has. It is guaranteed that the sum of these integers doesn't exceed $ 3·10^{5} $ . The fourth line contains single integer $ m $ ( $ 0<=m<10^{10000} $ ) — the amount in tugricks Byteasar needs to pay.
输出格式
Print single integer — the number of ways to pay exactly $ m $ tugricks modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
1
4
2
输出样例 #1
1
输入样例 #2
2
1
4 4
2
输出样例 #2
3
输入样例 #3
3
3 3
10 10 10
17
输出样例 #3
6