Problem 30: Sum of Substrings
Problem Statement: Given a numeric string, compute the sum of all possible substrings of the string taken as numbers. Since the answer can be very large, output it modulo 10^9+7.
Input
A single line containing a numeric string.
Output
Print the sum of all substrings modulo 10^9+7.
Examples
Input:
16
Output:
23
Solution in C++
#include <iostream>
#include <string>
using namespace std;
const long long MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
long long n = s.size();
long long sum = 0, f = 1;
long long res = 0;
// f[i] stores contribution factor for digit at index i from right end
// We use reverse iteration.
for (int i = n - 1; i >= 0; i--) {
int digit = s[i] - '0';
sum = (sum + (long long)(i + 1) * f) % MOD;
res = (res + digit * sum) % MOD;
f = (f * 10 + 1) % MOD;
}
cout << res % MOD << "\n";
return 0;
}