题意，给一串带问号的数字，要你把问号换成数字，把n构造成k的最小的倍数，并且n不能有前导零。
这个超级坑爹，输入自己有前导零的，有毒。
一开始想了很久不知道怎么搞，觉得看起来像以前的数位dp，只不过这个不是问[l,r]之间的数的数量，不需要考虑什么上界的限制，只需要确定余数。
从最低位开始数位dp的话，不知道是怎么样才能构造最小，所以只能够从最高位开始构造，这样就蛮麻烦的。
用类似bool数组的办法来记录每个余数种类的可行性。每次最高位的dp值保存两个信息，首先是它的上一步是谁（用来复原方案），然后就是它这一路选过的数字的大小在这一层里面的名次（用来贪心转移到下一层）。
最后回答答案的时候，要注意是要减去每个位的值，因为存的余数是“从最高位开始的前缀和”，当然是要反过来减掉。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1005];
char dp[1005][10][1005];
int qpow(int x, int n, int m) {
int res = 1;
while(n) {
if(n & 1)
res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
int pow10[1005];
typedef pair<int, pair<int, int> > pii;
pii p[2][100005];
int ptop[2];
int ans[1005];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n, k;
while(~scanf("%d%d", &n, &k)) {
scanf("%s", s + 1);
if(n == 1) {
if(s[1] == '?')
puts("0");
else {
int x = s[1] - '0';
if(x % k == 0)
puts(s + 1);
else
puts("-1");
}
continue;
}
if(s[1] == '0') {
puts("-1");
continue;
}
pow10[0] = 1;
for(int i = 1; i <= n; ++i) {
pow10[i] = pow10[i - 1] * 10 % k;
}
memset(dp, -1, sizeof(dp));
ptop[1] = 0;
if(s[1] != '?') {
int curj = s[1] - '0';
int curk = pow10[n - 1] * curj % k;
dp[1][curj][curk] = 10;
p[1][++ptop[1]] = {10, make_pair(curj, curk)};
} else {
for(int curj = 1; curj <= 9; ++curj) {
int curk = pow10[n - 1] * curj % k;
dp[1][curj][curk] = 10;
p[1][++ptop[1]] = {10, make_pair(curj, curk)};
}
}
for(int i = 2; i <= n; ++i) {
int cntl = 0;
register int pre = (i - 1) & 1, cur = (i & 1);
ptop[cur] = 0;
sort(p[pre] + 1, p[pre] + 1 + ptop[pre]);
if(s[i] != '?') {
int curj = s[i] - '0';
for(int pj = 1; pj <= ptop[pre]; ++pj) {
int prej = p[pre][pj].second.first;
int prek = p[pre][pj].second.second;
int curk = (prek + pow10[n - i] * curj) % k;
if(dp[i][curj][curk] == -1) {
dp[i][curj][curk] = prej;
p[cur][++ptop[cur]] = {++cntl, make_pair(curj, curk)};
}
}
} else {
for(int pj = 1; pj <= ptop[pre]; ++pj) {
for(int curj = 0; curj <= 9; ++curj) {
int prej = p[pre][pj].second.first;
int prek = p[pre][pj].second.second;
int curk = (prek + pow10[n - i] * curj) % k;
if(dp[i][curj][curk] == -1) {
dp[i][curj][curk] = prej;
p[cur][++ptop[cur]] = {++cntl, make_pair(curj, curk)};
}
}
}
}
}
register int cur = (n & 1);
sort(p[cur] + 1, p[cur] + 1 + ptop[cur]);
int res = -1;
for(int pj = 1; pj <= ptop[cur]; ++pj) {
int curj = p[cur][pj].second.first;
int curk = p[cur][pj].second.second;
if(curk == 0) {
res = curj;
break;
}
}
if(res != -1) {
int curj = res, newj = -1;
int curk = 0, newk = -1;
for(int i = n; i >= 1; --i) {
ans[i] = curj;
newj = dp[i][curj][curk];
newk = ((curk - pow10[n - i] * curj) % k + k) % k;
curj = newj;
curk = newk;
}
for(int i = 1; i <= n; ++i)
printf("%d", ans[i]);
printf("\n");
} else
puts("-1");
}
}