Submarine in the Rybinsk Sea (easy edition) CodeForces - 1195D1 (算贡献)

题目

https://cn.vjudge.net/problem/CodeForces-1195D1

This problem differs from the next one only in the presence of the constraint on the equal length of all numbers a1,a2,…,an. Actually, this problem is a subtask of the problem D2 from the same contest and the solution of D2 solves this subtask too.

A team of SIS students is going to make a trip on a submarine. Their target is an ancient treasure in a sunken ship lying on the bottom of the Great Rybinsk sea. Unfortunately, the students don’t know the coordinates of the ship, so they asked Meshanya (who is a hereditary mage) to help them. He agreed to help them, but only if they solve his problem.

Let’s denote a function that alternates digits of two numbers f(a1a2…ap−1ap,b1b2…bq−1bq), where a1…ap and b1…bq are digits of two integers written in the decimal notation without leading zeros.

In other words, the function f(x,y) alternately shuffles the digits of the numbers x and y by writing them from the lowest digits to the older ones, starting with the number y. The result of the function is also built from right to left (that is, from the lower digits to the older ones). If the digits of one of the arguments have ended, then the remaining digits of the other argument are written out. Familiarize with examples and formal definitions of the function below.

For example:
f(1111,2222)=12121212
f(7777,888)=7787878
f(33,44444)=4443434
f(555,6)=5556
f(111,2222)=2121212
Formally,

if p≥q then f(a1…ap,b1…bq)=a1a2…ap−q+1b1ap−q+2b2…ap−1bq−1apbq;
if p<q then f(a1…ap,b1…bq)=b1b2…bq−pa1bq−p+1a2…ap−1bq−1apbq.
Mishanya gives you an array consisting of n integers ai. All numbers in this array are of equal length (that is, they consist of the same number of digits). Your task is to help students to calculate ∑ni=1∑nj=1f(ai,aj) modulo 998244353.

Input
The first line of the input contains a single integer n (1≤n≤100000) — the number of elements in the array. The second line of the input contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array. All numbers a1,a2,…,an are of equal length (that is, they consist of the same number of digits).

Output
Print the answer modulo 998244353.

Examples

Input

1
2
3
12 33 45

Output

1
26730

Input

1
2
2
123 456

Output

1
1115598

Input

1
2
1
1

Output

1
11

Input

1
2
5
1000000000 1000000000 1000000000 1000000000 1000000000

Output

1
265359409

思路

碰到这种题目怎么老是往暴力模拟的方向去想呢?暴力模拟肯定不行啊!

这是简单版本的。可以知道给出每个数的位数都是相同的,那么按照题意给定的组合方法就是这些数中任意两个数每位数交替组合成一个新数,把这些新数全部加起来mod一个数得到答案。

而按照题意给定的组成新数的规则,我们可以大概模拟这样的情形。

当一个数(记为a,那么位数为a1a2a3……an)遇到另一个数(记为b,位数为b1b2b3……bn)时,那么数a就会变成为a10a20a30……an0,其中0的位置依次被数b的每位数插入。

而如果数a被其他的数遇到呢?就会变成这样。
0a10a20a30……an,0的位置也是依次被别的数插入。

如此一来,对于每个数,都有两种状态,即上面说的两种,遇到其他数和被其他的数遇到。

而对于每个数的每种状态,都需要和数组中每个数去组合成新数,也就是每个数的每个状态都有被使用n次,这些都要被加到结果里面,这就是算答案贡献了。

代码

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
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
const int MAXN=1e5+10;
const ll MOD=998244353;

ll arr[MAXN];
ll a[MAXN],b[MAXN];
int n;
ll len=0;
void length(ll x) {
while(x) x/=10,len++;
}
ll f1(ll x) {
ll j=10;
ll ans=0;
for(ll i=1;i<=len;i++) {
ans=ans+x%10*j;
j*=100;
x/=10;
}

return ans;
}
ll f2(ll x) {
ll j=1;
ll ans=0;
for(ll i=1;i<=len;i++) {
ans=ans+x%10*j;

j*=100;
x/=10;

}

return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&arr[i]);

length(arr[1]);
ll ans=0;
for(int i=1;i<=n;i++) {
a[i]=f1(arr[i])%MOD;
b[i]=f2(arr[i])%MOD;
ans=(ans+n*a[i]%MOD)%MOD;
ans=(ans+n*b[i]%MOD)%MOD;
}
printf("%lld\n",ans);
return 0;
}
-------------本文结束感谢您的阅读-------------
0%