# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22873 | AJAE (#40) | Unifying Values (KRIII5_UV) | C++14 | 6 ms | 2700 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 <iostream>
#include <set>
#include <algorithm>
#include <vector>
#define MOD 1000000007
#define ll long long
using namespace std;
ll d[10005];
ll nu[10005];
ll fact[10005] = { 1,1 };
int main() {
for (int i = 2; i <= 10000; i++)
fact[i] = (fact[i - 1] * i) % MOD;
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &d[i]);
nu[i] = nu[i - 1] + d[i];
}
ll ans = 0;
int zerochk = 0;
set <int> chk;
for (int i = 1; i < n; i++) {
if (chk.find(nu[i]) != chk.end()) continue;
chk.insert(nu[i]);
ll s = nu[i];
if (s == 0) {
int count = 0;
ll nz = 0;
for (int j = i + 1; j < n; j++) {
nz += d[i];
if (nz == 0) count++;
}
ans = (ans + fact[count]) % MOD;
}
else {
if (nu[n] / s > n - i + 1 || nu[n] % s != 0)
continue;
ll fin = 1;
vector<ll> next(n + 1), dp(n + 1);
dp[0] = dp[1] = 1;
next[0] = next[1] = 1;
for (int j = i + 1; j <= n; j++) {
if (nu[j] % s == 0) {
ll x = nu[j] / s;
if (x < 1) continue;
if (x <= fin + 1) {
dp[x] = next[x - 1];
next[x] += dp[x];
fin = max(x, fin);
}
}
}
ans = (ans + dp[nu[n] / s]);
}
}
printf("%lld", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |