2019 Multi-University Training Contest 6 11 Dimensions DP 求第k大m的倍数

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;
}