1018 Subnumbers

Statement

Metadata

作者: CAO, Peng
单位: Google
代码长度限制: 16 KB
时间限制: 200 ms
内存限制: 64 MB

Given a positive integer $N$ , let us define a subnumber of $N$ as a consecutive number of digits NOT starting with 0. For example if $N = 1021$ , it has 7 subnumbers, namely, 1, 10, 102, 1021, 2, 21 and 1 (again). Here is your task: please calculate the sum of all the subnumbers of $N$ . For 1021, the sum is 1+10+102+1021+2+21+1 = 1158. Since the result may be very large, output the answer modulo 1000000007 ( $10^9 + 7$ ) please.

Input Specification

Each input file contains one test case, which gives the integer $N$ ( $0 < N < 10^{100000}$ ) in a line.

Output Specification

Print in a line the sum of all $N$ 's subnumbers (modulo 1000000007).

Sample Input

1234567890123456789

Sample Output

332876913

Solution

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
char s[N];
void chadd(ll &x, ll y) {
    x += y;
    while (x >= mod) x -= mod;
    while (x < 0) x += mod;
}

int main() {
    while (scanf("%s", s + 1) != EOF) {
        ll res = 0, pre = 0, cnt = 0;
        for (int i = 1; s[i]; ++i) {
            int num = s[i] - '0';
            pre = pre * 10 % mod;
            if (num)
                ++cnt;
            chadd(pre, cnt * num);
            chadd(res, pre);
        }
        printf("%lld\n", res);
    }
    return 0;
}

Last update: May 4, 2022