1018 Subnumbers (35)（35 分）
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⁹

7. please.
   Input Specification:

Each input file contains one test case, which gives the integer N (0 < N < 10¹⁰⁰⁰⁰⁰) in a line.

Output Specification:

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

Sample Input:

1234567890123456789
Sample Output:

332876913

emmmm又是小水题。
感觉pat顶级的难度差异是不是有一点大啊。

对于一个数，考虑它对res的贡献

统计一下每个数的前缀和（突然想到好像只要统计一次10^0加到10N的和，然后可以乘每个数就行了。多开了十倍的空间。。。。。。）
然后统计一下前缀非0数的个数，搞一下就行了。
代码如下

#include <bits/stdc++.h>
using namespace std;
#define N (int)1e5+10
char arr[N];
typedef long long ll;
ll pre[10][N];
int pren[N];
const int mod = 1000000007;
void init()
{
	ll i, j;
	for (i = 1; i <= 9; i++)
	{
		pre[i][0] = i;
		for (j = 1; j < N; j++)
		{
			pre[i][j] = (pre[i][j-1] * 10) % mod + i;
		}
	}
	
}
int main(void)
{
	init();
	scanf("%s", arr+1);
	ll res = 0;
	int i; int len = strlen(arr+1);
	pren[0] = -1;
	for (i = 1; i <= len; i++)
	{
		if (arr[i] != 48) pren[i] = pren[i-1]+1;
		else pren[i] = pren[i-1];
	}
	for (i = 1; i <= len; i++)
	{
		if (arr[i] == 48) continue;
		res = (res + pre[arr[i]-48][len-i]*(pren[i]+1)) % mod;
	}
	cout << res;
}