P4999 烦人的数学作业 题解

· · 题解

P4999 烦人的数学作业 题解

思路分析

这里有一种数位分治（可能）的方法（根本不是我不会数位 dp）。

在 P2602 [ZJOI2010] 数字计数 中，众所周知地可以使用把 12 位数字拆分为两个 6 位。

代码

在本题中，如果我们直接以根号的复杂拆分，会得到 2 \times 10^{9} 的优秀优杂度以及一堆常数。

但我们可以分三次啊！

这么拆分后，复杂度来到了 3 \times 10^{6}，但加上 t 和累计答案的巨大常数会让 \texttt{\#17 \#20} 获得 TLE。

这时，我们便可以非常自然地想到了再分一次……

那么把 18 分为 5 + 5 + 4 + 4，复杂度为 2 \times 10^5 + 2 \times 10^4 以及小常数。

具体的实现如下：

首先将 l 不断增加，直到 l \mod 10^5 = 0。

然后将 r 不断减小，直到 r \mod 10^5 = 99999。

如果 l > r，退出

l \gets \frac{l}{10^5}, r \gets \frac{r}{10^5}

注意：在第一二步时，如果不是第一次，我们需要加上我们跳过部分的和，同时 l 的贡献是我们跳过数的数量。

重复以上步骤并加大模数。

具体的实现可以看代码。

代码实现

#include <cstdio>
constexpr long long Mod = 1e9 + 7;
constexpr long long Sum2 = 2250000;
constexpr long long Sum3 = 999996857;
constexpr long long Sum4 = 955900007;
constexpr long long Step1 = 1e5;
constexpr long long Step2 = 1e5;
constexpr long long Step3 = 1e4;
constexpr long long Less1 = 99999;
constexpr long long Less2 = 99999;
constexpr long long Less3 = 9999;
int t;
long long l, r;
long long answer;
inline void add(long long x)
{
    answer += x;
    answer %= Mod;
}
inline void addAnswer(long long x, long long cnt = 1)
{
    for (; x != 0;)
    {
        add((x % 10) * cnt);
        x /= 10;
    }
}
inline void solve()
{
    answer = 0;
    scanf("%lld%lld", &l, &r);
    // Step 1: 1 ~ 10^5
    for (; l % Step1 != 0 && l <= r;)
    {
        addAnswer(l);
        l++;
    }
    for (; r % Step1 != Less1 && r >= l;)
    {
        addAnswer(r);
        r--;
    }
    if (l > r)
    {
        printf("%lld\n", answer);
        return;
    }
    l /= Step1;
    r /= Step1;
    // Step 2: 10^5 ~ 10^10
    for (; l % Step2 != 0 && l <= r;)
    {
        add(Sum2);
        addAnswer(l, Step1);
        l++;
    }
    for (; r % Step2 != Less2 && r >= l;)
    {
        add(Sum2);
        addAnswer(r, Step1);
        r--;
    }
    if (l > r)
    {
        printf("%lld\n", answer);
        return;
    }
    l /= Step2;
    r /= Step2;
    // Step 3: 10^10 ~ 10^14
    for (; l % Step3 != 0 && l <= r;)
    {
        add(Sum3);
        addAnswer(l, Step1 * Step2);
        l++;
    }
    for (; r % Step3 != Less3 && r >= l;)
    {
        add(Sum3);
        addAnswer(r, Step1 * Step2);
        r--;
    }
    if (l > r)
    {
        printf("%lld\n", answer);
        return;
    }
    l /= Step3;
    r /= Step3;
    // Step 4: 10^14 ~ 10^18
    for (; l <= r;)
    {
        add(Sum4);
        addAnswer(l, Step1 * Step2 * Step3);
        l++;
    }
    printf("%lld\n", answer);
}
int main()
{
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        solve();
    }
    return 0;
}