Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef int ll;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- //struct Centroid_decomposition {
- // vector<ll> tree, siz;
- // vector<bool> used;
- // vector<vector<ll>> gr;
- // ll root = -1;
- // Centroid_decomposition(ll n, vector<vector<ll>>& g) {
- // tree.resize(n);
- // siz.resize(n);
- // used.resize(n);
- // gr = g;
- // }
- // void sizes(ll v, ll p) {
- // siz[v] = 1;
- // for (ll& u : gr[v]) {
- // if (u != p && !used[u]) {
- // sizes(u, v);
- // siz[v] += siz[u];
- // }
- // }
- // }
- // ll centroid(ll v, ll p, ll s) {
- // for (ll& u : gr[v]) {
- // if (u != p && !used[u] && siz[u] > s / 2) {
- // return centroid(u, v, s);
- // }
- // }
- // return v;
- // }
- // void build(ll v, ll p) {
- // sizes(v, -1);
- // used[v] = 1;
- // tree[v] = p;
- // for (ll& u : gr[v]) {
- // if (!used[u]) {
- // build(centroid(u, -1, siz[u]), v);
- // }
- // }
- // }
- // void build_tree() {
- // ll v = 0;
- // sizes(v, -1);
- // build(centroid(v, -1, siz[v]), -1);
- // gr.clear();
- // gr.resize(tree.size());
- // used.clear();
- // siz.clear();
- // for (ll v = 0; v < (ll)tree.size(); v++) {
- // if (tree[v] == -1) {
- // root = v;
- // continue;
- // }
- // gr[v].push_back(tree[v]);
- // gr[tree[v]].push_back(v);
- // }
- // }
- //};
- //const ll LG = 17;
- //const ll N = 1e5 + 1;
- //ll up[LG][N], d[N];
- //ll t = 0;
- //vector<vector<ll>> g;
- //vector<ll> clr;
- //
- //void dfs(ll v, ll p) {
- // if (p == -1) {
- // d[v] = 0;
- // up[0][v] = 0;
- // }
- // else {
- // d[v] = d[p] + 1;
- // }
- // for (ll l = 1; l < LG; l++) {
- // up[l][v] = up[l - 1][up[l - 1][v]];
- // }
- // for (ll& u : g[v]) {
- // if (u != p) {
- // up[0][u] = v;
- // dfs(u, v);
- // }
- // }
- //}
- //ll get_lca(ll a, ll b) {
- // if (a == b)return a;
- // if (d[b] > d[a])swap(a, b);
- // for (ll i = LG - 1; i >= 0; i--) {
- // if (d[up[i][a]] >= d[b]) a = up[i][a];
- // }
- // if (a == b) return a;
- // for (ll i = LG - 1; i >= 0; i--) {
- // if (up[i][a] != up[i][b]) a = up[i][a], b = up[i][b];
- // }
- // return up[0][a];
- //}
- //ll get_dist(ll a, ll b) {
- // ll lca = get_lca(a, b);
- // return d[b] + d[a] - 2 * d[lca];
- //}
- //struct Node {
- // // color dists to vertex with key color
- // map<ll,multiset<ll>> colors;
- //};
- //struct Node_help {
- // // color - num_vertex
- // vector<pll> colors;
- //};
- //vector<Node_help> centroid_build_vertex;
- //vector<Node> centroid_vertex;
- //void dfs_build_distance(ll v, ll p, vector<vector<ll>> ¢roid_tree) {
- // centroid_build_vertex[v].colors.push_back({ clr[v],v });
- // centroid_vertex[v].colors[clr[v]].insert(0);
- // for (ll& u : centroid_tree[v]) {
- // if (u == p)continue;
- // dfs_build_distance(u, v, centroid_tree);
- // if ((ll)centroid_build_vertex[v].colors.size() < centroid_build_vertex[u].colors.size()) {
- // centroid_build_vertex[v].colors.swap(centroid_build_vertex[u].colors);
- // }
- // for (pll& i : centroid_build_vertex[u].colors) {
- // centroid_build_vertex[v].colors.push_back(i);
- // }
- // //centroid_build_vertex[u].colors.clear();
- // }
- // for (pll& i : centroid_build_vertex[v].colors) {
- // centroid_vertex[v].colors[i.first].insert(get_dist(i.second, v));
- // }
- //}
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- ll n;
- cin >> n;
- vector<ll> a(n);
- for (ll i = 0; i < n; i++) {
- cin >> a[i];
- }
- vector<ll> cnt(1000);
- cnt[0] = 1;
- ll ans = 0, sum1 = 0, sum2 = 0;
- for (ll i = 0; i < n; i++) {
- sum2 += a[i];
- sum2 %= 999;
- ll j = i - 100;
- if (j >= 0) {
- sum1 += a[j];
- sum1 %= 999;
- cnt[sum1]++;
- ans += cnt[sum2];
- }
- }
- cout << ans - 1;
- //ll n;
- //cin >> n;
- //g.resize(n);
- //clr.resize(n);
- //for (ll i = 0; i < n - 1; i++) {
- // ll x;
- // cin >> x;
- // g[x].push_back(i + 1);
- // g[i+1].push_back(x);
- //}
- //for (ll i = 0; i < n; i++) {
- // cin >> clr[i];
- //}
- //dfs(0, -1);
- //centroid_vertex.resize(n);
- //centroid_build_vertex.resize(n);
- //Centroid_decomposition U(n, g);
- //U.build_tree();
- //dfs_build_distance(U.root, -1, U.gr);
- //for (ll i = 0; i < U.tree.size(); i++) {
- // cout << U.tree[i] << ' ';
- //}
- //cout << '\n';
- //for (ll i = 0; i < n; i++) {
- // cout << i << " :\n";
- // for (pll& j : centroid_build_vertex[i].colors) {
- // cout << j.second << " " << j.first << " dist :" << get_dist(j.second, i) << '\n';
- // }
- // cout << "colors\n";
- // for (auto it : centroid_vertex[i]) {
- // cout << it.first << ' ';
- // cout
- // }
- // cout << '\n' << '\n';
- //}
- //ll q;
- //cin >> q;
- //ll Node_cent_tree = U.root;
- //while (q--) {
- // ll v, c;
- // cin >> v >> c;
- // ll it = v;
- // ll ans = INT_MAX;
- // while (U.tree[it] != -1) {
- // if (!centroid_vertex[it].colors[c].empty()) {
- // auto x = *centroid_vertex[it].colors[c].begin();
- // ans = min(ans, x + get_dist(v, it));
- // }
- // it = U.tree[it];
- // }
- // /*if (ans == INT_MAX) {
- // cout << -1 << '\n';
- // }
- // else {
- // cout << ans << '\n';
- // }*/
- //}
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement