Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38358 申东铉 【S】T1 C++ 运行出错 0 1 MS 2600 KB 1233 2025-10-03 15:12:24

Tests(0/10):


#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 1e9 + 7; int n,a[100005],fa[100005]; vector <int> e[100005]; int dp[100005][3]; inline int pw (int x,int y) { y %= (mod - 1); int r = 1; while (y) { if (y & 1) { r *= x; r %= mod; } x *= x; x %= mod; y >>= 1; } return r; } int ny; inline void dfs (int u) { int x = 0,sum = 0; for (auto v : e[u]) { if (v == fa[u]) { continue; } dfs(v); x |= a[v]; sum += a[v]; sum % mod; dp[u][0] += (dp[v][0] + dp[v][1]) * ny; dp[u][0] %= mod; } dp[u][1] = dp[u][0]; dp[u][0] = (dp[u][0] + (a[u] + (a[u] ^ x)) * ny) % mod; dp[u][0] = (dp[u][0] - a[u] * pw(ny,e[u].size())) % mod; dp[u][0] = (dp[u][0] + mod) % mod; dp[u][1] = (dp[u][1] + x * ny) % mod; dp[u][1] = (dp[u][1] - sum * pw(ny,e[u].size())) % mod; dp[u][1] = (dp[u][1] + mod) % mod; return; } signed main () { freopen("pi.in","r",stdin); freopen("pi.out","w",stdout); ny = pw(2,mod - 2); cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } for (int i = 2;i <= n;i++) { cin >> fa[i]; e[fa[i]].push_back(i); } dfs(1); cout << dp[1][0] * pw(2,n - 1) % mod << endl; return 0; }


测评信息: