11 Dimensions(DP+剪枝)

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6644

题目大意

一个长度为n的字符串,其中有若干位为?,现在有q次询问,每次询问需要构造第k大的能被m整除的字符串。

解题思路

设 dp[i][j] 表示 [1, i − 1] 这些位的数字已经确定,且 [1, i − 1] 的数字模 m = j 时,有多少种在 [i, n] 这些位填数字的方法使得最终的数字模 m = 0。
可以发现第构造第1e18大的字符串并不需要太多的‘?’所以我们从后往前dp,发现大于1e18就停止,这一位之前的问号肯定全都要填0,后面的可以利用之前dp出来的数据贪心的求解。

代码

#include <bits/stdc++.h>

const long long maxn = 5e4 + 100;
const long long mod=1e9+7;
using namespace std;

char s[maxn];
unsigned long long dp[maxn][30];
int main() {
    ios::sync_with_stdio(false);
    unsigned long long t;
    cin>>t;
    while(t--) {
        unsigned long long n,m,q;
        cin>>n>>m>>q;
        cin>>s;
        unsigned long long st=0;
        for(int i=0; i<=n; i++) {
            for(int j=0; j<=m; j++) {
                dp[i][j]=0;
            }
        }
        dp[n][0]=1;
        for(int i=n-1; i>=0; i--) {
            if(s[i]=='?') {
                for(int j=0; j<m; j++) {
                    for(int k=0; k<=9; k++) {
                        dp[i][j]+=dp[i+1][(10*j+k)%m];
                    }
                }
            } else {
                for(int j=0; j<m; j++) {
                    dp[i][j]=dp[i+1][(10*j+(s[i]-'0'))%m];
                }
            }
            if(dp[i][0]>1e18||i==0) {
                st=i;
                break;
            }
        }
        unsigned long long sum=0,psum=0;
        for(int i=0; i<st; i++) {
            if(s[i]=='?') {
                sum=(sum*10)%mod;
                psum=(psum*10)%m;
            } else {
                sum=(sum*10+s[i]-'0')%mod;
                psum=(psum*10+s[i]-'0')%m;
            }
        }
        unsigned long long x;
        while(q--) {
            cin>>x;
            if(dp[st][0]<x) {
                cout<<"-1"<<endl;
                continue;
            }
            unsigned long long ans=sum,pre=psum;
            for(int i=st; i<n; i++) {
                if(s[i]=='?') {
                    for(int j=0;j<10;j++){
                        if(dp[i+1][(pre*10+j)%m]>=x){
                            pre=(pre*10+j)%m;
                            ans=(ans*10+j)%mod;
                            break;
                        }
                        else
                            x-=dp[i+1][(pre*10+j)%m];
                    }
                } else {
                    ans=(ans*10+s[i]-'0')%mod;
                    pre=(pre*10+s[i]-'0')%m;
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注