题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6644

题目：

t个测试样例，每个测试样例给出长度为n的字符串，其中包含数字和❓（保证首位不为❓），要求把❓替换成0-9，使得这个数可以整除m，q个询问，每次询问第k小的数是多少，没有的话输出-1

1≤T≤10000，1≤n≤50000,2≤m≤20,1≤q≤100000，1≤ki≤1018

input:

1

5 5 5

2??3?

1

2

3

100

10000

output:

20030

20035

20130

24935

-1

解题思路：

假设问号位上能填的数是1，3，5，那么总共有3！个满足条件的数，又可以算出20！是第一个大于1e18的，因为k最大是1e18，所以最终并不需要考虑字符串中的所有问号，只需要考虑后几十位的问号就可以了，比如只考虑后30位的问号(其实只考虑后20位的问号就能过）,那么后30位之前的问号其实都是0。

（1）逆序处理字符串(下标从0开始)，统计出问号出现的位置和对应的“权重”,并记录由已存在的数字得到的余数和数值。

比如字符串2？？345？2:

（2）dp[i][j]表示第i个问号前的所有问号的余数是j 对应的方法数，i即上表中的j。最终的方法数为dp[cnt][0]，cnt是问号个数。

递推式：dp[i][j] = dp[i-1][(j+quan[i] *x)%m] ，x是第i个问号上填的数

⚠️方法数可能很大，超过1e18，要让方法数最大能达到的值比1e***

（3）从第cnt个问号遍历到第1个问号，依次填数，并记录最终的数值，根据当前位置的问号填入数x后剩余的方法数来判断应该填那个数。

BTW：队友tql了?

ac代码：

略丑?‍♀️

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 5e4 + 5;
const ll MAX = 1e18+10;
int t, n, m, q, cnt, rem;
char s[maxn];
ll pos[maxn], quan[maxn];
ll dp[40][30];//dp[i][j],表示第i个？左侧的？形成的余数是j，有dp[i][j]种方法数
ll qpow(ll a, ll b)//a^b
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
void get_dp()
{
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= cnt; i++)
    {
        for(int j = 0; j < m; j++)
        {
            for(int x = 0; x <= 9; x++)
            {
                if(i == 1)
                {
                    if(((quan[i] * x) % m + j + rem) % m == 0)
                        dp[i][j]++;
                }
                else
                {
                    dp[i][j] += dp[i - 1][(j + (quan[i] * x) % m) % m];
                    if(dp[i][j] < 0||dp[i][j] >= MAX) // 方法数过大，让它最大比1e***一点，若dp[i][0]= MAX,那么存在第1e18小的数
                        dp[i][j] = MAX;

                }
            }
        }
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d", &n, &m, &q);
        scanf("%s", s);
        ll p1 = 1, p2 = 1, val = 0;
        cnt = 0, rem = 0;
        for(int i = n - 1; i >= 0; i--)//倒序遍历，记录？的位置和"权重"
        {
            if(isdigit(s[i]))
            {
                val = (val + ((s[i] - '0') * p1) % mod) % mod;
                rem = (rem + ((s[i] - '0') * p2) % m) % m;
            }
            else if(cnt <= 30)
            {
                pos[++cnt] = n - i - 1;//下标从0开始，记录在十进制中位数的下标，方便做10^x运算
                quan[cnt] = p2;
                //printf("cnt:%d pos:%d quan:%d\n", cnt, pos[cnt], quan[cnt]);
            }
            p1 = (p1 * 10) % mod;
            p2 = (p2 * 10) % m;//(a * b) % m = ((a % m) * (b % m)) % m
        }
        get_dp();
        ll k;
        while(q--)
        {
            scanf("%lld", &k);
            if(k > dp[cnt][0]) printf("-1\n"); //超过最大的方法数
            else//从高位的？向低位的？开始填数
            {
                ll ans = val, pre_rem = 0;//pre_rem 记录i位之前的？所形成的余数
                for(int i = cnt; i >= 1; i--)
                {
                    for(int x = 0; x <= 9; x++)
                    {
                        if(i == 1)
                        {
                            if(((quan[i] * x) % m + rem + pre_rem) % m == 0)
                            {
                                k--;
                                if(!k)
                                {
                                    ans = (ans + (x * qpow(10, pos[i])) % mod) % mod;
                                    break;
                                }
                            }
                        }
                        else // i > 1
                        {
                            int now_rem = ((quan[i] * x) % m + pre_rem) % m;
                            if(dp[i - 1][now_rem] < k)
                            {
                                k -= dp[i - 1][now_rem];
                            }
                            else //后面的方法数 >= k（k是变化后的）
                            {
                                pre_rem = now_rem;
                                ans = (ans + (x * qpow(10, pos[i])) % mod) % mod;
                                break;
                            }
                        }
                    }
                }
                printf("%lld\n", ans);
            }

        }
    }
    return 0;
}