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<iostream>
#include<algorithm>
#include<math.h>
#define MOD 1000000007
using namespace std;
long long int Data[10010];
long long int Sum[10010];
long long int ans;
long long int m_pow(long long int a, long long int b)
{
long long int s = 1;
for (long long int i = 0; i < b; i++)
{
s *= a;
s %= MOD;
}
return s;
}
int main()
{
long long int n;
cin >> n;
for (long long int i = 0; i < n; i++)
{
cin >> Data[i];
if (i == 0)Sum[i] = Data[i];
else
Sum[i] = Sum[i - 1] + Data[i];
}
long long int target = 0;
for (long long int i = 0; i < n - 1; i++)
{
target += Data[i];
if (target == 0 && (Sum[n - 1] - Sum[i]) != 0)continue;
if ((Sum[n - 1] - Sum[i]) < 0 && target > 0)continue;
if ((Sum[n - 1] - Sum[i]) > 0 && target < 0)continue;
if (target != 0 && (Sum[n - 1] - Sum[i]) % target != 0)continue;
long long int Zero = 0;
long long int tmp_sum = 0;
long long int Zero_sum = 1;
int flag = 0;
if (target == 0)
{
for (long long int j = i + 1; j < n; j++)
{
if (Data[j] == 0)Zero++;
else
{
tmp_sum += Data[j];
if (tmp_sum == 0)Zero++;
}
}
ans += (m_pow(2, Zero) - 1);
ans %= MOD;
}
else
{
for (long long int j = i + 1; j < n; j++)
{
tmp_sum += Data[j];
if (tmp_sum == target)
tmp_sum = 0;
if (Data[j] == 0)Zero++;
else
{
if (flag == 0)
{
flag = 1;
Zero = 0;
}
else if (flag == 1)
{
if (j == n - 1)continue;
Zero_sum *= (Zero + 1);
Zero = 0;
Zero_sum %= MOD;
}
}
}
if (tmp_sum != 0)continue;
ans += Zero_sum;
ans %= MOD;
}
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |