解説

https://yukicoder.me/submissions/500440

下位問題があるので、そちらがまだならそちらを解いてから、こちらを考えるといい。
基本的には、下位問題と似たような感じになる。
数列の要素を数字根を計算して、その総和に対して更に数字根を計算しているのだが、
これは数列の要素の総和mod9としてしまっていい。
10⁹+7問題なので、とりあえずDPを考えてみる。
dp[i] := i番目の要素まで確定してる時の組合せ
dpでやる必要もないのだが、実装しやすかったので使っている。

問題が、[10^L, 10^R)で9で割った余りがmoである数が何個あるかということになる。
count(L, R, mo) := [10^L, 10^R)で9で割った余りがmoである数が何個か
これを計算しよう。
まず簡単のために1からの区間で考えるようにしよう
count(r, mo) := [1, 10^r)で9で割った余りがmoである数が何個あるか
すると、count(L, R, mo) = count(R, mo) - count(L, mo)となる。

count(r, mo)の答えは(10^r-1)/9となる。
mod上ではうまく切り捨てとかはしてくれないので、適当にやってはいけないのだが、今回は10^rという制約が効いており、
うまくこの式でやれる。（余りの種類によって個数は変わらない、一様に分布してるので）

int N; ll L[101010], R[101010]; int D[101010];
mint dp[101010];
//---------------------------------------------------------------------------------------------------
mint count(ll r, int mo) {
    if (r == 0) return 0;
    return ((mint(10) ^ r) - 1) / 9;
}
mint count(ll L, ll R, int mo) {
    return count(R, mo) - count(L, mo);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> L[i];
    rep(i, 0, N) cin >> R[i];
    rep(i, 0, N) cin >> D[i];

    dp[0] = 1;
    bool allzero = true;
    int mo = 0;
    rep(i, 0, N) {
        if (D[i] == 0) {
            if (allzero) dp[i + 1] = dp[i];
        }
        else {
            D[i] %= 9;
            if (mo == D[i] && !allzero) dp[i + 1] += dp[i];
            rep(nxt, 0, 9) if ((mo + nxt) % 9 == D[i]) dp[i + 1] += dp[i] * count(L[i], R[i], nxt);
            allzero = false;
            mo = D[i];
        }
    }
    cout << dp[N] << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

桁和の桁和2 [yukicoder 1086]

解説