题意：给一个由若干个‘?’和一些数字组成的数S，和一个数N，现在要求在？处填数，使其能够整除N并且值最小。
分析：用DP[i][j]表示后i位组成的数，能否构成模N为j的数。
然后枚举记录一个前缀的和对n取模，判断一下是否存在dp[i+1][n-mod]=1就可以了。
#include <bits/stdc++.h> using namespace std; char s[1004]; bool dp[1004][1004]; int base[1004]; int main(){ int n; scanf("%s",s); int len = strlen(s); scanf("%d",&n); int sum = 1; dp[len][0]=1; base[0]=1; for (int i = 1; i <= len; ++i) { base[i] = base[i-1]*10%n; } for (int i = len - 1; i >= 0; --i) { if(s[i] == '?'){ for (int j = 0; j <= 9; ++j) { if(i == 0 && j == 0)continue; int temp = sum * j % n; for (int k = 0; k < n; ++k) { if(dp[i+1][k]){ dp[i][(k + temp)%n] = 1; } } } } else { int temp = s[i] - '0'; temp = temp * sum % n; for (int k = 0; k < n; ++k) { if(dp[i+1][k]){ dp[i][(k + temp)%n] = 1; } } } sum = sum * 10 % n; } sum = 0; bool yes = 1; for (int i = 0; i < len && yes; ++i) { if(s[i] == '?') for (int j = 0; j < 10; ++j) { if(i == 0 && j == 0)continue; int temp = sum + j*base[len - i - 1]%n; temp %= n; if(dp[i+1][(n - temp)%n]){ s[i] = j + '0'; break; } } if(s[i] == '?')yes = 0; else sum = (sum + (s[i]-'0')*base[len - i - 1]%n)%n; } if(yes)printf("%s",s); else printf("*\n"); }
