题解 UVA11361 【Investigating Div-Sum Property】

数位DP，对于每一个询问，回答为

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

设表示有位数（可以有前导）需要确定，需要让各位数字之和除以的余数为，需要让这位数组成的数字除以的余数为需要的方案数。然后我们一步一步确定前面几位数，加起来得到答案。

显然，我们可以从到枚举最高位上的数字，从而有:

边界:，

理解：要让位数各个位之和为，且第一位为，那么肯定需要没有的时候的值为为。第三个参数亦然。

几个细节：

记忆化搜索，那么时间复杂度为可是这么大怎么办？

如果中有位数，但是，显然没有合法的数字。因为所有位加起来都没有那么大，肯定加起来之后不能整除.

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

于是可以用数组来记搜，数字最多十位数，所以时肯定是无解的。数组可以开得下。

时答案为不为。

可以先让，然后紧贴求解答案，需要同时记录已经有的各位数字之和和总的数字之和。

还有一些细节见代码：

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