dp[i][j][k]表示第i位填数字k时，与后面的相连模数为j时，后面的数字最小填多少。
测得我提心吊胆还以为复杂度高了，结果出来46ms还是cf评测姬强啊。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <fstream>
#include <bitset>
#define init(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18;
template <typename T> void read(T &x) {
x = 0;
int s = 1, c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') s = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
x *= s;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
const int maxn = 1e3 + 5;
char str[maxn];
int p, st, m;
int dp[maxn][maxn][10], Tenpow[maxn];
int main() {
scanf("%s%d", str + 1, &p);
int n = strlen(str + 1);
for (int i = 1, t = 1; i <= n; i++, t = t * 10 % p) Tenpow[n - i + 1] = t;
init(dp, -1);
rep(i, 0, 9)
dp[n + 1][0][i] = 0;
irep(i, n + 1, 2)
irep(j, p - 1, 0) {
if (i == n + 1 && j) continue;
rep(k, 0, 9) {
if (dp[i][j][k] == -1) continue;
if (str[i - 1] != '?') {
int d = str[i - 1] - '0';
dp[i - 1][(d * Tenpow[i - 1] % p + j) % p][d] = k;
} else {
rep(t, 0, 9) {
dp[i - 1][(t * Tenpow[i - 1] % p + j) % p][t] = k;
}
}
break;
}
}
rep(i, 1, 9)
if (dp[1][0][i] >= 0) {
st = i;
break;
}
if (st) {
rep(i, 1, n) {
printf("%d", st);
int d = st;
st = dp[i][m][d];
m = (m - d * Tenpow[i] % p + p) % p;
}
} else puts("*");
return 0;
}