codeforces E Enigma (DP)

传送门](http://codeforces.com/group/xrTA2IaQje/contest/258354)
题意：给一个大数（长度小于1000）和一个n
但是这个大数的有些位用？表示不确定，现在要把所有？填上后使他是n的倍数，并且最小。
思路：简单DP
dp[i][j]表示使第i位模数的为j的最小值，然后模拟就可以了
要注意的是我们要从后往前dp！！！这样在还原的时候才能保证字典序最小
因为如果从前往后dp，我们在还原答案的时候是从后往前还原的。这样的话会优先让低位最小而不是有限让高位最小

#include<bits/stdc++.h>
using namespace std;
typedef long long L;
char s[2001];
L dp[2001][2001],n,l;
L val[2001];
L qp(L x,L y,L mod)
{
    L ans=1;
    while(y){
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
int main()
{
    cin>>s+1>>n;
    l=strlen(s+1);
    for(int i=l;i>=1;i--){
        if(s[i]=='?') val[i]=qp(10,l-i,n);
        else val[i]=(s[i]-'0')%n*qp(10,l-i,n)%n;
    }
 
    for(int i=1;i<=l+1;i++) for(int j=0;j<n;j++) dp[i][j]=INT_MAX;
    dp[l+1][0]=0;
    for(int i=l;i>=1;i--){
        if(s[i]=='?'){
            for(int j=0;j<=9;j++){
                if(i==1&&j==0) continue;
                for(int k=0;k<n;k++){
                    if(dp[i+1][k]!=INT_MAX){
                        dp[i][(k+val[i]*j%n)%n]=min(dp[i][(k+val[i]*j%n)%n],j*1ll);
                    }
                }
            }
        }
        else {
            int c=s[i]-'0';
            for(int k=0;k<n;k++){
                if(dp[i+1][k]!=INT_MAX){
                    dp[i][(k+val[i])%n]=c;
                }
            }
        }
    }
 
    if(dp[1][0]!=INT_MAX) {
        int now=0;
        for(int i=1;i<=l;i++) {
            printf("%lld",dp[i][now]);
            int w=dp[i][now]*qp(10,l-i,n)%n;
            now=((now-w)%n+n)%n;
 
        }
        printf("\n");
    }
    else printf("*\n");
}