4.7爆蛋模拟赛T1&&CF242E XOR on Segment

发表于 | 阅读次数：

4.7爆蛋模拟赛

T1：

【题目描述】

给一个正整数 N，我们定义“子数”字是 N 的一段非 0 开头的连续数字。
举个例子，如果 N=1021，它有 7 个“子数”，分别是“1”, “10”,“102”,“1021”,
“2”,“21”和“1”(可重复)。
现在给你一个任务：请计算所有“子数”的和。
对于 N=1021 来说，“子数”和等于 。
结果可能非常巨大，输出答案对 $1000000007$ 取模。

【输入格式】

第一行一个数 T。
接下来 T 行每行一个数表示 n。

【输出格式】

输出 T 行每行一个整数表示这个数的子数。

【样例输入】

2
1234567890123456789
1021

【样例输出】

40% :1<=n<= $10^{200}$ T<=100

100%:1<=n<=$10^{100000}$ T<=100

分析

我们从后面开始考虑

每次加进去一个数，那么这个数对答案所产生的贡献肯定是

$\sum_{j=0}^{i-1} 10^{j} \ast a[i]\ast a[i]前面不为零的数字的个数$

这很显然，加进去一个不为零的数会使这个数多算一次。

预处理10的幂

$O(TN)$回答

合算$O(能过)$

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int L=10000000;
char ppp[L];
char *p1,*p2;
inline char gc()
{
	if(p1==p2)
	{
		p2=(p1=ppp)+fread(ppp,1,L,stdin);
	}
	return *p1++;
}
//#define getchar gc
inline void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
	
}
inline void write(const int x)
{
	int tmp=x;
	char ggg[10001];
	int s=0;
	if(tmp==0)
	{
		putchar('0');
		return ;
	}
	if(tmp<0)
	{
		putchar('-');
		tmp=-tmp;
	}
	while(tmp>0)
	{
		ggg[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(ggg[--s]);
	}
}
const int mod=1e9+7;
int shi[100010],a[100010],now[100010];
char s[100010];
int ans;
signed main()
{
	shi[0]=1;
	for(register int i=1;i<=100000;++i)
	{
		shi[i]=(shi[i-1]*10+1)%mod;
	}
	
	int tt;
	read(tt);
	while(tt--)
	{
		int ss=0;
		char ch=getchar();
		while(ch<'0'||ch>'9')
		{
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
		{
			s[++ss]=ch;
			ch=getchar();
		}
		ans=0;
		memset(now,0,sizeof(now));
		for(register int i=1;i<=ss;++i)
		{
			a[i]=s[i]-'0';
			if(a[i])
			{
				now[i]=now[i-1]+1;
			}
			else 
			now[i]=now[i-1];
		}
		for(register int i=ss;i>=1;--i)
		{
			ans+=(a[i]*shi[ss-i]*now[i])%mod;
		}
		write(ans%mod);
		puts("");
	}
}