UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#193881#3398. countshiruiheng100281ms2808kbC++111.1kb2023-10-14 17:43:202023-10-14 18:39:55

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll n, a[100010], tmp[100] = {0, 1}, cnt[100], ans, col[100010];
unordered_map<ll, int> mp;
int check(ll x){
	if(mp[x])
		return mp[x];
	int cnt = 0;
	while(x > 0){
		x /= 10;
		cnt++;
	}
	return mp[x] = cnt;
}
int main(){
	for(int i = 2 ; i <= 10 ; i++)
		tmp[i] = tmp[i - 1] * 10;
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
		if(n > 1000){
			col[i] = upper_bound(tmp + 1, tmp + 11, a[i]) - tmp - 1;
			cnt[col[i]]++;
		}
	}
	if(n <= 1000){
		ans = 0;
		for(int i = 1 ; i <= n ; i++)
			for(int j = 1 ; j <= n ; j++){
				if(i == j)
					continue;
				//cout << a[i] * tmp[check(a[j])] << " \n"[j == n];
				ans += a[i] * tmp[check(a[j]) + 1] + a[j];
				ans %= mod;
			}
		cout << ans;
		exit(0);
	}
	for(int i = 1 ; i <= n ; i++){
		ans += (a[i] * (n - 1)) % mod;
		ans %= mod;
		for(int j = 1 ; j <= 10 ; j++)
			if(cnt[j] > 1 || (cnt[j] == 1 && col[i] != j))
				ans = (ans + (a[i] * tmp[j + 1] % mod * (cnt[j] - (col[i] == j))) % mod) % mod;
	}
	cout << ans;
	return 0;
} 

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 20
Accepted
time: 65ms
memory: 1304kb

input:

1000
332109541 265698305 339007233 386487277 65597920 217218907 436378017 221884663 270433433 268014...

output:

675688319

result:

ok single line: '675688319'

Test #2:

score: 20
Accepted
time: 55ms
memory: 1304kb

input:

1000
108652253 396843081 18739163 168730297 41598432 22132831 155692945 617160601 164753707 86147692...

output:

653845876

result:

ok single line: '653845876'

Test #3:

score: 20
Accepted
time: 56ms
memory: 1308kb

input:

1000
71158753 11073019 119630785 162780801 25368543 517705 123835636 254874371 4127795 157084999 201...

output:

126629477

result:

ok single line: '126629477'

Test #4:

score: 20
Accepted
time: 58ms
memory: 1304kb

input:

1000
496106605 30223789 139619196 52432001 12405522 405765988 35664524 102798391 192246625 760951562...

output:

891456070

result:

ok single line: '891456070'

Test #5:

score: 20
Accepted
time: 47ms
memory: 2808kb

input:

100000
227552529 170886571 513851125 46675201 188079376 255537313 266819605 69661658 214521435 33384...

output:

677195751

result:

ok single line: '677195751'