Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.3 kB
1
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];
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));
        for (int i=0; i<=MAX_N; i++) {
            visit[i].clear();
            arr[i] = false;
        }
    }

    return 0;
}
Leave a Comment