This way
題意：
給你一個不完整的數，知道它有n位，是m的倍數，總共q個詢問，每次問你它第k大是多少。
題解：
dp[i][j]表示到第i位的時候，模m為j時的個數。
我們用res表示目前枚舉到的數模m是多少，然後枚舉前面模m的餘數，
那麼狀态轉移方程就是
d p [ i ] [ ( r e s + k ) % m ] + = d p [ i − 1 ] [ k ] ; dp[i][(res+k)\%m]+=dp[i-1][k]; dp[i][(res+k)%m]+=dp[i−1][k];
注意它是會爆ll的，那麼我們需要讓他在一個k達不到的值即可。
然後我們枚舉後20位，因為 1 0 18 ∗ 20 < 1 0 20 10^{18}*20<10^{20} 1018∗20<1020
對于目前一位，我們檢視它之後一位而不是它本身，因為這一位取模之後我不知道它是從哪些地方轉移過來的，但是确定了這一位的值，那麼我就知道下一位是從哪裡轉移過來的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e4+5;
const ll mod=1e9+7;
const ll inf=2e18;
char s[N];
int a[N];
ll p_mod[N],p_m[N],dp[N][21];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
scanf("%s",s);
ll ans=0,_m=0;
int cnt=0;
for(int i=0;i<n;i++)
{
if(s[i]!='?')
{
ans=(ans*10+(ll)(s[i]-'0'))%mod;
_m=(_m*10+(ll)(s[i]-'0'))%m;
}
else
ans=ans*10%mod,_m=_m*10%m;
}
for(int i=n-1;~i;i--)
if(s[i]=='?')
a[++cnt]=n-i-1;
p_mod[0]=p_m[0]=1;
for(ll i=1;i<=n;i++)
p_mod[i]=p_mod[i-1]*10%mod,p_m[i]=p_m[i-1]*10%m;
dp[0][0]=1;
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<m;j++)
dp[i][j]=0;
for(int j=0;j<=9;j++)
{
int res=j*p_m[a[i]]%m;
for(int k=0;k<m;k++)
{
dp[i][(res+k)%m]+=dp[i-1][k];
dp[i][(res+k)%m]>inf&&(dp[i][(res+k)%m]=inf);
}
}
}
_m=(m-_m)%m;
ll aa=ans;
while(q--)
{
ll k;
scanf("%lld",&k);
if(dp[cnt][_m]<k)
{
printf("-1\n");
continue;
}
ans=aa;
int now_m=_m,ne_m;
for(int i=min(20,cnt);i;i--)
{
for(ll j=0;j<=9;j++)
{
ne_m=(now_m-j*p_m[a[i]]%m+m)%m;
if(dp[i-1][ne_m]<k)
k-=dp[i-1][ne_m];
else
{
ans=(ans+p_mod[a[i]]*j)%mod;
now_m=ne_m;
break;
}
}
}
printf("%lld\n",ans);
}
}
return 0;
}