| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22258 | 2017-04-30T03:16:29 Z | AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya) | Unifying Values (KRIII5_UV) | C++ | 6 ms | 3224 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
int n;
lint a[10005];
vector<int> v[10005];
vector<lint> dyn[10005];
lint dabs(lint x){ return max(x, -x); }
lint solve(int x){
for(int i=0; i<=x; i++){
v[i].clear();
dyn[i].clear();
}
lint q = a[n] / x;
for(int i=0; i<=n; i++){
if(dabs(a[i]) % dabs(q) == 0){
v[a[i] / q].push_back(i);
}
}
for(int i=0; i<=x; i++){
if(v[i].size() == 0) return 0;
dyn[i].resize(v[i].size());
}
dyn[0][0] = 1;
for(int i=1; i<=x; i++){
int pt = 0;
lint sum = 0;
for(int j=0; j<v[i].size(); j++){
while(pt < v[i-1].size() && v[i-1][pt] < v[i][j]){
sum += dyn[i-1][pt];
pt++;
}
sum %= mod;
dyn[i][j] = sum;
}
}
return dyn[x].back();
}
int main(){
cin >> n;
for(int i=1; i<=n; i++){
lint x;
cin >> x;
a[i] = a[i-1] + x;
}
if(a[n] == 0){
lint ans = 1;
for(int i=1; i<n; i++){
if(a[i] == 0) ans = ans * 2 % mod;
}
cout << (ans + mod - 1) % mod;
return 0;
}
lint ret = 0;
for(int i=2; i<=n; i++){
if(a[n] % i == 0){
ret += solve(i);
}
}
cout << ret % mod;
}