题目链接

Description

For a positive integer \(n\), let us define \(f(n)\) as the number of digits in base \(10\).

You are given an integer \(S(1≤S≤10^8)\). Count the number of the pairs of positive integers \((l,r)\) \((l≤r)\) such that \(f(l)+f(l+1)+…+f(r)=S\), and find the count modulo \(10^9+7\).

题解

分两种情况讨论。

\(1.\ f(l)\leq 7\)

则至多有\(10^8/8=12500000\)个八位数，所以\(r\leq 22500000\).

因此，可以预处理出\(f[1..22500000]\)，然后采用 尺取法 得到 当\(f(l)\leq 7\)时 的\((l,r)\)组数.

\(2. \ f(l)\geq 8\)

此时，由 \(S\) 的限制，易知 \(f(r)-f(l)\leq 1\).

令 \(t=r-l+1\)，枚举 \(t\)

若 \(f(l)==f(r)\)

则显然要求 \(t|S\),

记\(N\)位数的个数右 \(D_N\) 个，则符合要求的 \((l,r)\) 组数为 \(D_{\frac{S}{t}}-t+1\)

若 \(f(r)-f(l)==1\)

设 \(len=f(l)\) 且长度为 \(len\) 的数字有 \(x\) 个，长度为 \(len+1\) 的数字有 \(y\) 个，则有

\[\begin{cases}
x+y=t\\
x*len+y*(len+1)=S
\end{cases}
\]

其中\(len=\lfloor\frac{S}{t}\rfloor\).

记\(S=tq+r\ (0\leq r\lt t)\)

则方程组可转化为

\[\begin{cases}
x+y=t\\
xq+y(q+1)=tq+r
\end{cases}
\]

所以有

\[\begin{cases}
x=t-r=t-S\%t\\
y=r=S\%t
\end{cases}
\]

即对每个\(t\)此时有且仅有一组解。

统计上述三部分的答案，即为最终答案。

Code

#include <bits/stdc++.h>

#define lim1 10000000

#define lim2 22500000

using namespace std;

typedef long long LL;

int f[lim2+10];

const LL mod = 1e9+7;

void init() {

    int l = 1, r = 10;

    for (int k = 1; k <= 7; ++k) {

        for (int i = l; i < r; ++i) f[i] = k;

        l = r; r *= 10;

    }

    for (int i = lim1; i <= lim2; ++i) f[i] = 8;

}

LL poww(LL a, LL b) {

    LL ret = 1;

    while (b) {

        if (b & 1) (ret *= a) %= mod;

        (a *= a) %= mod;

        b >>= 1;

    }

    return ret;

}

LL count1(LL x) {

    int l = 1, r = 1, ret = 0; LL sum = 0;

    while (true) {

        while (r <= lim2 && sum < x) sum += f[r++];

        if (sum < x) break;

        if (sum == x) (ret += 1) %= mod;

        sum -= f[l++];

        if (l == lim1) break;

    }

    return ret;

}

LL count2(LL x) {

    LL upp = x/8,

        ret = upp;

    for (int t = 1; t <= upp; ++t) {

        if (x % t == 0) {

            int len = x / t;

            LL sub = 9 * poww(10, len-1) % mod;

            (sub += mod - t) %= mod;

            (ret += sub) %= mod;

        }

    }

    return ret;

}

int main() {

    init();

    LL n;

    scanf("%lld", &n);

    LL ans1 = count1(n), ans2 = count2(n);

    printf("%lld\n", (ans1+ans2)%mod);

    return 0;

}

巴特西

AtCoder Regular Contest 090 F - Number of Digits