洛谷 4999 烦人的数学作业

发表于 | 分类于 |

为什么大家都拘泥于数字计数的做法呢……

这里给出记搜实现的另一种做法，记录位数、填过的所有数的和、是否贴着边界。

其实这题顶多蓝题。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 18;
const long long mod = 1e9 + 7;
int t;
long long l,r;
int d[LEN + 5],tot;
long long f[LEN + 5][LEN * 9 + 5];
long long dfs(int x,int sum,int top)
{
    if(!x)
        return sum;
    if(!top && ~f[x][sum])
        return f[x][sum];
    int bound = top ? d[x] : 9;
    long long ret = 0;
    for(register int i = 0;i <= bound;++i)
        ret = (ret + dfs(x - 1,sum + i,top && i == bound)) % mod;
    if(!top)
        f[x][sum] = ret;
    return ret;
}
long long solve(long long x)
{
    tot = 0;
    while(x)
        d[++tot] = x % 10,x /= 10;
    return dfs(tot,0,1) % mod;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",(solve(r) - solve(l - 1) + mod) % mod);
    }
}