Algorithm

HackerRank/Algorithm/Dynamic Programming/Sam And Substrings

Problem Summary

Given a string of integers, whose first character is not zero, find the sum of all substrings.

Solution

Let S be the given string and N be its length.

Let f[i] be the sum of substrings that ends at S[i]. For any positive i, there are two cases. One is S[i], the other is S[j…i] ( j < i). The sums of these two cases are respectively S[i] - ‘0’ and f[i-1] × 10 + i × (S[i] - ‘0’).

So we have

f[0] = S[0] - ‘0’
f[i] = f[i-1] × 10 + (i+1) × (S[i] - ‘0’) , for i = 1,2,…,N-1

The answer is the sum of f[0],f[1],…,f[N-1].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
const int maxn = 200002;
const int mo = 1e9+7;
int n;
char s[maxn];
long long f[maxn];
int main()
{
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++) s[i]-='0';
	f[0]=s[0];
	for(int i=1;i<n;i++)
		f[i] = (10*f[i-1] + s[i]*i + s[i]) %mo;
	long long ans=0;
	for(int i=0;i<n;i++)
		ans = (ans + f[i])%mo;
	printf("%lld\n", ans);
    return 0;
}