ABC177 C - Sum of product of pairs에서 배운
4190 단어 AtCoder파이썬AtCoderBeginnerContest
무심해졌지만, 우선
샘플도 읽는다.
과연.
예를 들어 ** 1 2 3 4가 주어지면
**1x2+(1+2)x3+(1+2+3)x4가 되지 않을까?
후에는 표현방법이 문제다.
하지만, tle & wa
ans.py
N = int(input())
A = list(map(int,input().split()))
score = A[0]*A[1]
for i in range(2,N): #計算量 O(N)
score += sum(A[:i])*A[i] #計算量 O(N)...合算してほぼ O(N^2)
score %= 7+10**9
print(score)
배열의 sum의 계산량은 배열 길이에 의존한다.
그래서 결국에는 그것만으로 O(N)이 될 수 있다.
라고 하는 것으로 재작성하면, 다녔다.
ans_r1.py
N = int(input())
A = list(map(int,input().split()))
X = sum(A)
score = 0
for i in range(N-1,0,-1):
score += (X-A[i])*A[i]
score %= 7+10**9
X -= A[i]
print(score)
Reference
이 문제에 관하여(ABC177 C - Sum of product of pairs에서 배운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/AKpirion/items/4162119826d348c8aedf텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
