Submission #2706083

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e18, 0<m<=1e9
	if(a==0){
		return 0;
	}
	long long int apow[30], c[30];
	for(int i=0; i<30; i++){
		if(i==0){
			apow[i]=a;
			c[i]=1;
		}else{
			apow[i]=apow[i-1]*apow[i-1]%m;
			c[i]=c[i-1]*2;
		}
	}
	long long int ans=1;
	for(int i=29; i>=0; i--){
		if(k>=c[i]){
			ans=ans*apow[i]%m;
		}
		k=k%c[i];
	}
	return ans;
}
 
ll inv(ll x, ll p){
  return powmod(x, p-2, p);
}

int main()
{
	int n;
  scanf("%d", &n);
  vector<int> v[200001];
  for(int i=1; i<=n; i++){
    int p1;
    scanf("%d", &p1);
    v[i].push_back(p1);
    v[p1].push_back(i);
  }
  int d[200001];
  fill(d, d+n+1, -1);
  d[0]=0;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int x=que.front();
    que.pop();
    for(int i=0; i<v[x].size(); i++){
      if(d[v[x][i]]<0){
        d[v[x][i]]=d[x]+1;
        que.push(v[x][i]);
      }
    }
  }
  vector<P> dist;
  for(int i=0; i<=n; i++){
    dist.push_back(P(d[i], i));
  }
  sort(dist.begin(), dist.end());
  int dmax=dist[n].first;
  ll p2=1;
  for(int i=0; i<=n; i++){
    p2*=2;
    p2%=MOD;
  }
  ll ans=0;
  ll c[200001];
  for(int t=0; t<=dmax; t++){
    auto itr=upper_bound(dist.begin(), dist.end(), P(t, 10000000));
    itr--;
    while(1){
      P p=*itr;
      int x=p.second;
      if(d[x]==t){
        c[x]=500000004;
        if(itr==dist.begin()) break;
        itr--;
        continue;
      }
      if(v[x].size()==1){
        c[x]=0;
        if(itr==dist.begin()) break;
        itr--;
        continue;
      }
      ll sum=0, prod=1;
      for(int i=0; i<v[x].size(); i++){
        int y=v[x][i];
        if(d[y]<d[x]) continue;
        sum+=(c[y]*inv((MOD+1-c[y])%MOD, MOD)%MOD);
        sum%=MOD;
        prod*=(MOD+1-c[y]);
        prod%=MOD;
      }
      c[x]=sum*prod%MOD;
      if(itr==dist.begin()) break;
      itr--;
    }
    ans+=c[0];
    ans%=MOD;
  }
  ans*=p2;
  ans%=MOD;
    printf("%lld\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:55:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p1);
                     ^

Judge Result