#include<bits/stdc++.h> usingnamespacestd; constint mod = 59964251; constint maxn = 1e5 + 5; intphi(int x) { int ans = 1; for (int i = 2; 1ll * i * i <= x; i++) { if (x % i == 0) { ans *= (i - 1); x /= i; } while (x % i == 0) { ans *= i; x /= i; } } if (x > 1) ans *= (x - 1); return ans; }
longlongqpow(longlong a, longlong b) { longlong ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b /= 2; } return ans; } bool notprime[maxn]; int mu[maxn]; int prime[maxn]; longlong wd[maxn]; voidinit() { mu[1] = 1; for (int i = 2; i < maxn; i++) { if (!notprime[i]) { prime[++prime[0]] = i; mu[i] = -1; } for (int j = 1; j <= prime[0] && 1ll * prime[j] * i < maxn; j++) { notprime[i * prime[j]] = true; if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } } }
intmain() { int t; cin >> t; init(); while (t--) { string b; cin >> b; longlong m, d, k; cin >> m >> d >> k; longlong p = phi(mod); longlong bb = 0; bool flag = 0; for (int i = 0; i < b.size(); i++) { bb = bb * 10 + (b[i] - '0'); if (bb >= p) { flag = true; bb %= p; } } if (flag) bb += p; longlong dd = qpow(d, k); dd = qpow(dd, bb) % mod; longlong res = 0; longlong m1 = m / d; for (int i = 1; i <= m / d; i++) wd[i] = (wd[i - 1] + qpow(i, k)) % mod; for (int i = 1; i <= m / d; i++) { longlong k1 = qpow(i, bb); k1 = qpow(k1, k); longlong x1 = wd[m1 / i]; x1 = qpow(x1, bb); res += mu[i] * k1 % mod * x1 % mod; res %= mod; } res = ((res % mod) + mod) % mod; res = res * dd % mod; cout << res << endl; } return0; }
#include<bits/stdc++.h> usingnamespacestd; constint maxn = 1e5 + 5; #define ull unsigned long long int a[maxn]; int n, k; vector<int> g[maxn]; vector<int> v[maxn]; ull val[maxn][4]; ull ans[maxn]; int f[maxn][30]; voiddfs1(int x, int fa) { f[x][0] = fa; for (int i = 1; i <= 25; i++) f[x][i] = f[f[x][i - 1]][i - 1]; for (auto to : g[x]) dfs1(to, x); }
voiddfs(int x, int l1, int l2) { for (int i = 0; i < 4; i++) val[x][i] = 0; for (auto to : g[x]) { dfs(to, l1, l2); for (int k = 0; k < 4; k++) val[x][k] += val[to][k]; } int k = ((a[x] >> l1) & 1) * 2 + ((a[x] >> l2) & 1); val[x][k] += 1; ull y = 1; if (l1 != l2) y = 2; ans[x] += y * (val[x][0] * val[x][3] + val[x][1] * val[x][2]) * (1ull << (l1 + l2)); for (auto to : v[x]) { int k = ((a[to] >> l1) & 1) * 2 + ((a[to] >> l2) & 1); val[x][k] -= 1; } }
intmain() { ios::sync_with_stdio(false); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i <= n; i++) { int u; cin >> u; g[u].push_back(i); } dfs1(1, 0); for (int i = 1; i <= n; i++) { int l = k; int x = i; for (int i = 0; i <= 25; i++) { if ((l >> i) & 1) x = f[x][i]; } v[x].push_back(i); } for (int i = 0; i <= 31; i++) { for (int j = 0; j <= i; j++) dfs(1, i, j); } for (int i = 1; i <= n; i++) cout << ans[i] << endl; return0; }
#include<bits/stdc++.h> usingnamespacestd; constint maxn = 1e5 + 5; #define ull unsigned long long int a[maxn]; int n, k; vector<int> g[maxn]; ull ans[maxn]; int len[maxn], son[maxn], p[maxn]; int now; ull num[maxn][4]; voiddfs1(int x) { for (auto to : g[x]) { dfs1(to); if (len[to] + 1 > len[x]) { len[x] = len[to] + 1; son[x] = to; } } }
voiddfs(int x, int l1, int l2) { p[x] = ++now; for (int j = 0; j < 4; j++) num[p[x]][j] = 0; if (son[x]) { dfs(son[x], l1, l2); for (int j = 0; j < 4; j++) num[p[x]][j] += num[p[son[x]]][j]; } int y = ((a[x] >> l1) & 1) * 2 + ((a[x] >> l2) & 1); num[p[x]][y] += 1; for (auto to : g[x]) { if (to == son[x]) continue; dfs(to, l1, l2); for (int j = 0; j < 4; j++) num[p[x]][j] += num[p[to]][j]; for (int i = 0; i <= len[to]; i++) { for (int j = 0; j < 4; j++) num[p[x] + i + 1][j] += num[p[to] + i][j]; } } ull wd = 1 + (l1 != l2); if (len[x] > k) { ull y1 = 1ull * (num[p[x]][0] - num[p[x] + k + 1][0]) * (num[p[x]][3] - num[p[x] + k + 1][3]); ull y2 = 1ull * (num[p[x]][1] - num[p[x] + k + 1][1]) * (num[p[x]][2] - num[p[x] + k + 1][2]); ans[x] += wd * (y1 + y2) * (1ull << (l1 + l2)); } else ans[x] += wd * (num[p[x]][0] * num[p[x]][3] + num[p[x]][1] * num[p[x]][2]) * (1ull << (l1 + l2)); }
intmain() { ios::sync_with_stdio(false); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i <= n; i++) { int u; cin >> u; g[u].push_back(i); } dfs1(1); for (int i = 0; i <= 31; i++) { for (int j = 0; j <= i; j++) { now = 0; dfs(1, i, j); } } for (int i = 1; i <= n; i++) cout << ans[i] << endl; return0; }