提出 #23743953

---

ソースコード 拡げる

MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))

# SUM[i]=sum(A[:i])
SUM=[0]
for a in A: SUM.append(SUM[-1]+a)

# SUM[i]%j==sum[x]%j となるような i 未満の最大の x が idx[i][j]、存在しなければ -1
idx=[[-1]*(N+1) for _ in range(N+1)]

# 直前に SUM[x]%i==j となった x が pre[i][j]、存在しなければ -1
pre=[[-1]*(N+1) for _ in range(N+1)]

for i in range(N+1):
  for j in range(1,N+1):
    idx[i][j]=pre[j][SUM[i]%j]
    pre[j][SUM[i]%j]=i

# DP[i][j] = i 番目までを j 個に区切る場合の数
DP=[[0]*(N+1) for i in range(N+1)]
DP[0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    if idx[i][j]!=-1:
      DP[i][j]=(DP[idx[i][j]][j]+DP[idx[i][j]][j-1])%MOD

print(sum(DP[N])%MOD)

提出情報

ジャッジ結果