题解|数字游戏2

数位dp

题意相信大家都懂（不懂就继续读吧学好文化课吧），接下来看数据范围

1<=a,b<=231

显然，枚举是会T掉的，所以我们考虑数位dp（注意：我是用前缀和来处理出答案的，也就是最终答案为ans_b-ans_a-1）。

1.状态的设置

    首先，因为是数位dp，所以状态的第一位肯定是数位。接着，我们再来分析题目，看有什么东西是必须记录的。然而，因为这一题的状态十分明显，就是各个数字之和，所以我们就直接拿这个和当作第二维的状态。最终的状态就是f[i][j]，代表有i位，数字和为j且满足题目所求（数字和modN为0）的数字的个数有多少个

2.转移方程

    和基本的数位dp没有区别，我们也是采用记忆化搜索来进行状态转移。在搜索过程中，我们从0到尽可能的高位（为什么这么说？请见后面的3.a）中选择一个数。设选择的数为k，则对于每一个k，f[i][j]+=f[i+1][j+k]。状态转移方程也有了。但，接下来还有一些

3.需要注意的地方&优化

    a.选择数的时候，当前位能选的最大的数

       我们来看一个例子：设最多能选的数是2234。在某次搜索过程中，我们的当前状态是2???，那么此时次高位只能选0~2；但在另一次搜索过程中，当前状态为1???，这时的次高位却能选0~9。这种选择范围的差异是由于前一位选的数字导致的，所以我们设置一个bool，用来记录前一位是否与x的前一位相等，若不相等，则能选的数为0～9，相等就是0~x的当前位。

    b.状态的优化

       注意到，其实题目只是要求所选的数的数字和modN为0即可，所以我们可以将状态的第二维优化一下，改成j%N，这样就可以节省很多空间。

到此，这道题就被解决了。接下来就是代码了

#include<cstdio>
#include<cstring>
long a,b,n,ans,c[12],len,f[12][102];
long dfs(int pos,int rest,bool limit)
{
    if(pos>len)return rest==0;
    if(!limit&&f[pos][rest]!=-1)return f[pos][rest];
    long ret=0,res=limit?c[len-pos+1]:9;
    for(long i=0;i<=res;i++)ret+=dfs(pos+1,(rest+i)%n,limit&&i==res);
    return !limit?f[pos][rest]=ret:ret;
}
long part(long x)
{
    memset(f,-1,sizeof(f));
    len=0;
    while(x)c[++len]=x%10,x/=10;
    return dfs(1,0,1);
}
int main()
{
    while(scanf("%ld%ld%ld",&a,&b,&n)!=EOF)//多组数据
    {
        ans=part(b)-part(a-1);
        printf("%ld\n",ans);
    }
}