| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22892 | pichulia | Unifying Values (KRIII5_UV) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define I 16384
#define M 1000000007
typedef pair<long long int, int> pii;
int n;
long long int a[10009];
long long int s[10009];
long long int res;
map<long long int, vector<int> > xx;
set<long long int> ss;
long long int ms[2 * I];
void update_ms(int i, long long int k) {
ms[i + I] = k%M;
i = i + I;
i /= 2;
while (i > 0) {
ms[i] = (ms[i * 2] + ms[i * 2 + 1]) % M;
i /= 2;
}
}
long long int get_ms(int dep, int ql, int qr, int ll, int rr) {
if (rr < ql || qr < ll) return 0;
if (ql <= ll && rr <= qr) { return ms[dep]; }
return (get_ms(dep * 2, ql, qr, ll, (ll + rr) / 2) + get_ms(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr)) % M;
}
void process(long long int x) {
int i, j, k, l;
long long int m;
if (s[n] == 0) m = -1;
else {
m = s[n] / x;
if (m > n) return;
if (m < 2) return;
}
int cur, nxt;
cur = 0; nxt = 1;
int si = n+2;
for (i = 0; i < 2 * I; i++)
ms[i] = 0;
for (i = 1; i <= n; i++)
{
if (s[i] == x)
{
update_ms(i, 1);
}
}
if (m > 1) {
xx.clear();
for (i = 1; i <= n; i++) {
if (s[i] % x == 0 && s[i]/x>0) {
xx[s[i]].push_back(i);
}
}
for (k = 2; k <= m; k++) {
long long int cur = k*x;
for (i = ((int)xx[cur].size()) - 1; i >= 0; i--) {
long long int kk = get_ms(1, 0, xx[cur][i], 0, I - 1);
update_ms(xx[cur][i], kk);
}
for (i = ((int)xx[cur-x].size()) - 1; i >= 0; i--) {
update_ms(xx[cur-x][i], 0);
}
}
res = (res + ms[n + I]);
}
else
{
int ss = 0;
for (i = 1; i < n; i++) { if (s[i] == 0)ss++; }
res = 1;
for (i = 0; i < ss; i++) { res = (res * 2) % M; }
res = (res - 1 + M) % M;
}
}
int main() {
int i, j, k, l;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
}
res = 0;
for (i = 1; i < n; i++) {
if (s[n] == 0 && s[i] == 0) {
if (ss.find(s[i]) != ss.end()) continue;
ss.insert(s[i]);
process(0);
}
else if (s[i] != 0 && s[n] % s[i] == 0 && s[n] / s[i] > 1) {
if (ss.find(s[i]) != ss.end()) continue;
ss.insert(s[i]);
process(s[i]);
}
}
printf("%lld\n", res);
return 0;
}