当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6644:11 Dimensions

题目描述
11 Dimensions is a cute contestant being talented in math. One day, 11 Dimensions came across a problem but didn't manage to solve it. Today you are taking training here, so 11 Dimensions turns to you for help.

You are given a decimal integer $S$ with $n$ bits $s_1s_2\dots s_n(0\leq s_i\leq 9)$, but some bits can not be recognized now(replaced by ``$\texttt{?}$''). The only thing you know is that $S$ is a multiple of a given integer $m$.

There may be many possible values of the original $S$, please write a program to find the $k$-th smallest value among them. Note that you need to answer $q$ queries efficiently.
输入解释
The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.

In each test case, there are three integers $n,m,q(1\leq n\leq 50000,2\leq m\leq 20,1\leq q\leq 100000)$ in the first line, denoting the length of $S$, the parameter $m$, and the number of queries.

In the second line, there is a string $s$ of length $n$, denoting the given decimal integer $S$. It is guaranteed that $s_i$ is either an integer within $[0,9]$ or ``$\texttt{?}$'', and $s_1$ is always an integer within $[1,9]$.

For the next $q$ lines, each line contains an integer $k_i(1\leq k_i\leq 10^{18})$, denoting each query.

It is guaranteed that $\sum n\leq 500000$ and $\sum q\leq 10^6$.
输出解释
For each query, print a single line containing an integer, denoting the value of $S$. If the answer exists, print $S\bmod(10^9+7)$ instead, otherwise print ``$\texttt{-1}$''.
输入样例
1
5 5 5
2??3?
1
2
3
100
10000
输出样例
20030
20035
20130
24935
-1
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6644

最后修改于 2020-10-25T23:33:06+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
8000/8000MS(Java/Others) 524288/524288K(Java/Others)