题解 UVA11361 【Investigating Div-Sum Property】

数位DP,对于每一个询问,回答为ask(B)-ask(A-1).

我主要想分享一下一些实现上的细节。但还是先说一下思路,这里借鉴了《算法竞赛入门经典:训练指南》的讲解。

f(w,m_1,m_2)表示有w位数(可以有前导0)需要确定,需要让各位数字之和除以K的余数为m_1,需要让这w位数组成的数字除以K的余数为m_2需要的方案数。然后我们一步一步确定前面几位数,加起来得到答案。

显然,我们可以从09枚举最高位上的数字head,从而有:

f(w,m_1,m_2)=\sum f(w-1,(m_1 - head)mod \, K,(m_2 - 10^{w-1}head)mod \,K).

边界:f(0,0,0)=1f(0,m_1 ≠0,m_2≠ 0)=0.

理解:要让w位数各个位之和mod \, Km_1,且第一位为head,那么肯定需要没有head的时候mod \, K的值为为(m_1-head)mod \, K。第三个参数亦然。

几个细节:

1.记忆化搜索,那么时间复杂度为O(ws* K^2).可是K这么大怎么办?

如果ask(val)valws位数,但是K > 9* ws,显然没有合法的数字。因为所有位加起来都没有K那么大,肯定加起来之后不能整除K.

所以题中数据范围给那么大是没用的…..

于是可以用数组来记搜,数字最多十位数,所以K>9 * 10 =90时肯定是无解的。数组可以开得下。

2. val=0时答案为1不为0

3.可以先让val=val+1,然后紧贴val求解答案,需要同时记录已经有的各位数字之和和总的数字之和。

还有一些细节见代码:

#include<cmath>
#include<cstdio>
#include<cstring>
template<typename T>
inline bool read(T &x){
    x=0;char c;T  f=1;
    do{c=getchar();if(c=='-')f=-1;else if(c==EOF)return false;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    return x*=f,true;
}
long long A,B,K;
long long tp[20];//tp[i]表示10 的i次方
long long Div[20];
long long d[20][200][200];

#define res1 (d[w][m1][m2])
long long f(int w,int m1,int m2){
    if(w==0){
        return m1==0&&m2==0;
    }
    if(~d[w][m1][m2])return d[w][m1][m2];
    res1=0;
    for(register int  i=0;i<=9;++i){
        //i即为前所述的head 即最高位的数字
        res1+=f(w-1,(m1-i%K+K)%K,(m2-(1ll*tp[w-1]*i%K)+K)%K);
        //必须保证mod K之前为非负数 所以加上一个K 
    }
    return res1;
}
long long Getws(long long val){//分割这个数,并且返回它的位数

    if(!val){//其实这步可以不要。毕竟在GetAns()的入口处特判了0的情况
        return Div[0]=(Div[1]=0)+1;
    }
    Div[0]=0;
    while(val){
        Div[++Div[0]]=val%10;
        val/=10;
    }
    return  Div[0];
}
long long GetAns(long long val){
    if(!val)return 1ll;
    long long res=0;
    ++val;
    //紧贴val来计算答案,如果不加1会漏掉val这个数
    //当然也可以不加1,最后特判val这个数
    long long ws=Getws(val);
    if(ws*9<K)return 1ll;
    long long presum=0,presum2=0;
    //presum:当前累计的各位数字之和 如322的presum=3+2+2=7
    //presum2:当前已确定数字组成的数:如32***的presum2=32000.
    for(register int  i=ws;i>=1;--i){
        for(register int  j=0;j<Div[i];++j){
            if(j)presum+=1;presum%=K;
            if(j)presum2+=tp[i-1];presum2%=K;
            //presum,presum2每步取模更方便
            res+=f(i-1,(K-presum+K)%K,(K-presum2+K)%K);
            //此处有减法,必须保证它是非负数
        }
        //紧贴val来取值,则最高一位没有被讨论到
        //例如,如果val=32565
        //如果已经枚举到第二位
        //那么实际上我们暂时只会先考虑30***和31***的情况
        //但在后面的讨论中,应保证第二位为2
        //所以还要把2的贡献累加进去
        if(Div[i]){
            ++presum;
            presum2+=tp[i-1];
        }
    }
    return res;
}
void  work(){
    // GetAdd();
    long long ans=GetAns(B)-GetAns(A-1);
    printf("%lld\n",ans);
}
int main(){
    //freopen("testin.txt","r",stdin);
    //freopen("testout.txt","w",stdout);
    tp[0]=1;
    for(register int  i=1;i<=15;++i){
        tp[i]=10ll*tp[i-1];
    }
    long long T;
    read(T);
    while(T--){
        read(A);
        read(B);
        read(K);
        memset(d,-1,sizeof(d));
        work();
    }

    return 0;
}

加入对话

2条评论

    1. 因为没找到一个合适的插件…前两天我还发帖子求助来着,有位大佬提供了个方法,但还没来得及试。

留下评论

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