AtCoder Regular Contest 090: F - Number of Digits

https://atcoder.jp/contests/arc090/tasks/arc090_d

問題概要

正整数nに対してf(n)をnの10進表記での桁数と定義する。与えられる整数Sに対してf(l)+f(l+1)+...+f(r)=Sを満たすような(l, r)の組が何通り存在するか求めよ。

S <= 108

解法

まず桁数が少しでも大きくなると「ある桁全体を覆うような区間」はそれだけで簡単にSを超えてしまって解になりえない。具体的には8桁以上になると桁全体を覆う区間はSの上限108を超える( (108 - 107) * 8 ≒ 7×108 )。よってf(l)>=8のケースでは区間がある桁をまるまるまたぐということがありえないため、f(l)とf(r)の差はたかだか1にしかならない。これを元に以下のように場合分けをする。

(1) f(l) < 8 のとき

とりうる区間が結構面倒な形になりうるが、ここまでの大きさなら数列を陽に持った上で尺取りをやる形の全探索ができる。rの方は8桁の方に少し飛び出す可能性があることに注意する(厳密にやらずとも適当に5×107くらいまで持っておけばまあ足りる)。

(2) f(l) >= 8 のとき

区間の長さに注目すると、まずありうる区間長の範囲は1~S/8となる (f(l)の下限が8 => 長さ1の区間の最小値が8)。ここで区間長kを定めたとき、上述のとおりf(l)とf(r)の差はたかだか1であることから、f(l), f(l+1), ..., f(r) の並びは [S/k], [S/k], [S/k], [S/k]+1, [S/k]+1 のような形になる([]はここでは切り捨ての意)。つまり後半の(S%k)個が[S/k]+1, 前半の(K-S%K)個が[S/k]という形である。Sがkで割り切れないとき、このようなfの並びはただ一通りに定まる。よって1<=k<=S/8かつSの約数でないkの数だけ答えに+1が加わる。一方でSがkで割り切れるときはすべてが[S/k]となる。これはつまりf(l)=f(r)となるケースで、このときはその桁の中で好きに区間をとることができる。なのでこのケースをカバーするためにはSの約数を全部求めてf(l)を列挙すればよい。それぞれのf(l)について具体的な数は (l桁の数の個数 - 区間長 + 1) となる。このとき区間長が上述の範囲に収まっているかチェックする必要があることに注意する。

感想

説明ができなすぎる 解説放送を見て通したのでわかりたい人はそっちをみてくれ 小さいものだけ全探索で大きいときサボるといえば結構あるあるに聞こえるがサボり方がなんか自分にとってかなり非自明だった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

immutable long MOD = 10^^9 + 7;

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

long count(int x) {
    return ((powmod(10, x, MOD) - powmod(10, x-1, MOD)) % MOD + MOD) % MOD;
}

void main() {
    auto S = readln.chomp.to!int;
    long ans = 0;

    // f(l) <= 7
    {
        auto A = new int[](10^^7*5);
        for (int k = 1; k <= 8; ++k) {
            for (int i = 10^^(k-1); i < 10^^k && i < 10^^7*5; ++i) {
                A[i] = k;
            }
        }

        for (int l = 1, r = 1, cnt = 0; l < 10^^7; cnt -= A[l], l += 1) {
            if (r < l) r = l, cnt = 0;
            while (cnt < S) cnt += A[r], r += 1;
            if (cnt == S) (ans += 1) %= MOD;
        }
    }

    // f(l) >= 8
    {
        int[] factors;
        int T = S / 8;

        for (int i = 1; i * i <= S; ++i) {
            if (S % i != 0) continue;
            if (i * i != S) factors ~= S / i;
            factors ~= i;
        }

        foreach (f; factors) {
            if (S / f < 8) continue;
            (ans += count(S / f) - f) %= MOD;
            ans = (ans + MOD) % MOD;
        }

        (ans += T) %= MOD;
    }

    ans.writeln;
}