https://www.acmicpc.net/problem/10986
initial
obvious way is n^2 time but i tried optimising via a prefix sum and for each iteration of i in lst, i minus the previous i so like
from 1,3,6,7,9 I minus 1 from the prefix sum so it becomes like
0,2,4,6,8 then i iter through each number in this prefix sum and see if it is divisible by m and so on.
but it is time overtime
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
lst = list(map(int,input().split()))
prefix=[lst[0]]
for i in range(1,len(lst)):
prefix.append(lst[i]+prefix[i-1])
ans=0
for i in prefix:
if i%m==0:
ans+=1
for i in range(1,len(lst)):
for j in range(i,n):
prefix[j]-=lst[i-1]
if prefix[j]%m==0:
ans+=1
print(ans)solution
https://code-angie.tistory.com/26
i still dont get it
i get that we first make a list of size m and store the prefix sum % m in this list. So this list has the number of occurrences for remainder 0 to m-1.
Then, if remained is 0, we know that by itself it is already disible by m (like 3, 9, 69 that is divisble by m) so we just add that value, which is lst[0]. But
we can make further pairs via nC2, so as we iterate through from 0 to m-1 and make pairs via this nc2 formula.
But i get that when reamidner is 0, we can make pairs like 3-6, 6-9 like this but when remainder is 1, we can indeed pairs like 1-7 but it is still not divisble by 3! how can we add this as answer?
