# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22871 | 크리님 제가 귀여우면 됬지 뭘 더 원하세요 진짜 (#40) | Unifying Values (KRIII5_UV) | C++11 | 6 ms | 2444 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<bits/stdc++.h>
using std::vector;
using std::pair;
const long long MOD = 1000000007;
std::set<long long> set;
long long arr[10010];
long long sum[10010];
long long cnt[10010];
long long abss(long long a) {
if (a < 0)return -a;
return a;
}
int sign(long long a) {
if (a > 0)return 1;
if (a < 0)return -1;
return 0;
}
long long poww(long long a, long long b) {
if (b == 0)return 1;
long long tmp = pow(a, b / 2);
if (b % 2 == 1)return (((tmp*tmp) % MOD)*a) % MOD;
return (tmp*tmp) % MOD;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &arr[i]);
sum[i] = sum[i - 1] + arr[i];
}
long long p = sum[n];
long long ans = 0;
long long zero = 0;
if (p < 0) {
for (int i = 1; i <= n; i++) {
sum[i] = -sum[i];
}
p = sum[n];
}
for (int i = 1; i <= n; i++) {
if (sum[i] == 0)zero++;
if (sum[i] != 0 && set.count(sum[i]) == 0) {
if ( p%sum[i] == 0 && sign(p)==sign(sum[i])) {
set.insert(sum[i]);
long long k = p / sum[i];
if (k > n || k == 1)break;
for (int j = 1; j <= k; j++) {
cnt[j] = 0;
}
cnt[0] = 1;
for (int j = i; j <= n; j++) {
if (sum[j] % sum[i] == 0 && sum[j]!=0 && sign(sum[j])==sign(sum[i])) {
long long q = sum[j] / sum[i];
assert(q >= 1);
cnt[q] += cnt[q - 1];
cnt[q] %= MOD;
}
}
ans += cnt[k];
ans %= MOD;
}
}
}
if(sum[n]==0)
ans += poww(2, zero - 1) - 1;
printf("%lld", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |