Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.5 kB
2
Indexable
Never
#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];
set<int> visit[MAX_N];
int arr[MAX_N];

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

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

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) { 
        memset(a, 0, sizeof(a));
        for (int i=0; i<MAX_N; i++) {
            visit[i].clear();
            arr[i] = -1;
        }

        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

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

        ll ans = n*n + n;
        for (int i=1; i<=n; i++) {
            if ((visit[1].find(i) == visit[1].end())) {
                ans += n; 
                continue;
            }

            for (int j=1; j<=n; j++) {
                if (i!=j) {
                    if ( arr[j]==1 && (visit[j].find(i) == visit[j].end()) && i<j) {
                        ans++;
                    }
                }
            }
        }
        cout << ans << '\n';
        
    }

    return 0;
}
Leave a Comment