문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든 수의 합

D - Another Sigma Problem (atcoder.jp)

D - Another Sigma Problem

 

 

배열 A의 모든 순서쌍 (A[i],A[j])에 대하여 f(A[i],A[j])를 A[i]A[j]라고 정의

 

예를 들어 f(10,1) = 101이고 f(3,14) = 314

 

i < j인 모든 가능한 f(A[i],A[j])의 합을 구해서 998244353으로 나눈 나머지를 구하는 문제

 

예를 들어

 

3 14 15라면 (3,14), (3,15), (14,15) 3개의 순서쌍에 대해 314, 315, 1415가 있고 이들의 합은 2044

 

모든 순서쌍을 찾는 것은 기본적으로 $O(N^{2})$인데 N이 20만이라 시간초과일 것이고

 

O(N)으로 푸라는 말인데 그냥 생각하면 대단히 어렵다...

 

수식을 생각해봐야한다.

 

그리고 "이어붙인 수"하면 10진법으로 한번 바꿔볼까? 정도 생각해보는게 좋은 것 같다.

 

이 테크닉이 되게 자주쓰이는것 같다

 

123 = 1*10^2 + 2*10^1 + 3 처럼 바꿔보는게 어떨까? 이 말

 

예를 들어 f(3,14) = 314 = 3*10^2 + 14, f(20,150) = 20150 = 20*10^3 + 150...

 

그래서 f(x,y)를 하면 x에 y를 이어붙이는데 x 뒤에 0을 이어 붙인 다음 y를 더한 것인데

 

0을 얼마나 붙여야할까? y의 길이만큼 붙여야 x에 y를 그대로 붙인 것과 같겠지

 

 

 

 

[a1,a2,a3,a4] 4개의 수가 있다고 해보자.

 

a1을 기준으로 f(a1,a2) + f(a1,a3) + f(a1,a4) = a1*10^len(a2) + a2 + a1*10^len(a3) + a3 + a1*10^len(a4) + a4

 

a2를 기준으로 f(a2,a3) + f(a2,a4) = a2*10^len(a3) + a3 + a2*10^len(a4) + a4

 

a3을 기준으로 f(a3,a4) = a3*10^len(a4) + a4

 

이들을 다 더하면..?

 

a1*10^len(a2) + (a2+a3+a4)

 

+ (a1+a2)*10^len(a3) + (a3+a4)

 

+ (a1+a2+a3)*10^len(a4) + a4

 

자세히 보면 특이한 부분이 있다.

 

$$(a_{1} + a_{2} + ... + a_{i-1})*10^{len(a_{i})} + (a_{i} + a_{i+1} + ... + a_{n})$$

 

그리고 여기서 i = 2,3,4,...n으로 된다.

 

따라서 먼저 배열의 누적합 배열을 구한다면 a1+a2+...ai-1 = prefix[i-1]이랑

 

ai+ai+1...+an = prefix[n-1] - prefix[i-1]은 O(1)에 구할 수 있으므로 

 

전체를 O(N)에 구할 수 있게된다.

 

 

n = int(input())

A = list(map(int,input().split()))

prefix = [A[0]]

for i in range(1,n):
    
    prefix.append(prefix[-1]+A[i])

# a1 a2 a3 a4

# a1*(10^(len(a2))+10^(len(a3))+10^(len(a4))) + (a2+a3+a4)

# a2*(10^(len(a3))+10^(len(a4))) + (a3+a4)

# a3*(10^(len(a4)))+a4

v = 0

mod = 998244353

for i in range(1,n):
    
    v += (prefix[i-1]*10**(len(str(A[i]))) + (prefix[n-1] - prefix[i-1]))
    v %= mod

print(v)