【题解】Atcoder ARC#90 F-Number of Digits

　　Atcoder刷不动的每日一题...

　　首先注意到一个事实：随着 (l, r) 的增大，(f(r) - f(l)) 会越来越小。考虑暴力处理出小数据的情况，我们可以发现对于左端点 (f(l) <= 7) 的情况下，右端点的最大限度为 (frac{10^8}{8} + 10^7) 。这个范围并不大，可以直接用 two-pointer 处理出来。

　　那么这部分的数据和后面的数据有什么不同呢？当 (f(l) > 7) 的时候，(f(r) - f(l) <= 1)。那么设 (l = f(l))，我们有：

　　( x * l + y * (l + 1) = S )

令 ( t = x + y )

　原式等于 ( t * l + y = S )；

　　我们令 (x + y > y) ，即 ( x != 0 )，那么最后一个式子实际上表达的是 ( y = S mod t )。也就是说，对于任何的一个确定的 (t)，（当 (l) 的范围 (> 7)）我们都可以找到唯一对应的 (x, y) 与之对应。那么我们就可以扫一遍所有的 (t)以求得答案。注意当 ( y = 0 ) 时，对答案的贡献为这个数字范围内所有长为 (t) 的区间。

#include <bits/stdc++.h>
using namespace std;
#define maxn 23000000
#define int long long
#define mod 1000000007
int digit[maxn], ans, S;

int read()
{
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

int Qpow(int times)
{
    int x = 10, base = 1;
    for(; times; times >>= 1, x = x * x % mod)
        if(times & 1) base = base * x % mod;
    return base;
}

void Up(int &x, int y) { x = (x + y) % mod; }
signed main()
{
    S = read(); int lim = S / 8, now = 0;
    for(int i = 1; i < maxn; i ++) digit[i] = digit[i / 10] + 1;
    for(int i = 1, now = 0, tem = 0; i < 1e7; i ++)
    {
        while(tem < S) { tem += digit[now]; now ++; }
        if(tem == S) { ans += 1; if(ans >= mod) ans -= mod; } 
        tem -= digit[i];
    }
    for(int i = 1; i <= lim; i ++)
    {
        if(!(S % i)) 
        {
            int l = S / i, sum = Qpow(l - 1) * 9 % mod;
            Up(ans, (sum - i + 1 + mod) % mod);
        }
        else 
        { 
            int l = (S - S % i) / i;
            ans += 1; if(ans >= mod) ans -= mod; 
        }
    }
    printf("%lld
", ans);
    return 0;
}

【题解】Atcoder ARC#90 F-Number of Digits

相关推荐