Submission #66610919

---

Source Code Expand

"""
<方針>
- 円周上で三角形が正三角形になるときは、`+L//3` ずつしたところを確認すれば良い。
- また、`L%3 == 0` の時だけ正三角形が存在しうる。
- 最初の点は、`0~L//3` だけ確認すれば良い。
- 計算時間は `O(N+L)` になるはず。
"""
# 入力
N, L = map(int, input().split())
D = list(map(int, input().split()))

# 正三角形を生成できないとき
if(L%3 != 0):
  print(0)
  exit()

# 円周上に点を置く
ind = 0
C = [0]*L
C[0] += 1
for d in D:
  ind += d
  ind %= L
  C[ind] += 1

# カウントをする
ans = 0
# L//3だけ見れば良い
for i in range(L//3):
  X = C[i+0*L//3]
  Y = C[i+1*L//3]
  Z = C[i+2*L//3]
  
  ans += X*Y*Z

# 出力
print(ans)

Submission Info

Judge Result