Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- int mod=1000000007;
- vector<int> powers(int n){
- vector<int> q(n+1);
- q[0]=1;
- for (int i=1; i<=n; i++){
- q[i]=q[i-1]*2;
- q[i]%=mod;
- }
- return q;
- }
- void dfs(vector<vector<int>>& graph, vector<bool>& used, int u, vector<int>& c, vector<int>& ans, vector<int>& q){
- used[u]=true;
- c[u]=1;
- int a=0;
- for (int v:graph[u]){
- if (!used[v]){
- dfs(graph, used, v, c, ans, q);
- c[u]+=c[v];
- a-=(q[c[v]]-1);
- a%=mod;
- if (a<0){
- a+=mod;
- }
- }
- }
- a+=(q[c[u]]-1);
- a%=mod;
- if (a<0){
- a+=mod;
- }
- ans[u]=a;
- }
- signed main(){
- int t;
- cin>>t;
- while(t--){
- int n;
- cin>>n;
- vector<int> q=powers(2*n);
- vector<int> p(n);
- vector<vector<int>> graph(n);
- int x=0;
- for (int i=0; i<n; i++){
- cin>>p[i];
- p[i]--;
- if (p[i]!=i){
- graph[i].push_back(p[i]);
- graph[p[i]].push_back(i);
- }else{
- x=i;
- }
- }
- vector<int> c(n);
- vector<int> ans(n);
- vector<bool> used(n);
- dfs(graph, used, x, c, ans, q);
- int sum=0;
- for (int i=0; i<n; i++){
- sum+=(i+1)*ans[i];
- sum%=mod;
- }
- cout<<sum<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement