Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
4
Indexable
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#define MAX_N 200005
#define ll long long
using namespace std;

int n;
int a[MAX_N];
vector<set<int>> visit(MAX_N);
vector<bool> arr(MAX_N);

bool DFS(int start, int cur_id) {
    if (cur_id < 1 || cur_id > n) return true;

    visit[start].insert(cur_id);
    int next = cur_id + a[cur_id];

    if (visit[start].find(next) == visit[start].end()) {
        return DFS(start, next);    
    }
    else return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) { 
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        for (int i=1; i<=n; i++) {
            arr[i] = DFS(i, i);
        }

        ll ans = n*n + n;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (i!=j) {
                    if ( arr[j] && (visit[j].find(i) == visit[j].end()) ) ans++;
                }
            }
        }
        cout << ans << '\n';
        memset(a, 0, sizeof(a));
        visit.clear();
        arr.clear(); 
    }

    return 0;
}
Editor is loading...
Leave a Comment