QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191940 | #6125. Lucky Stars Management | ucup-team1209# | WA | 591ms | 151916kb | C++20 | 2.5kb | 2023-09-30 12:45:42 | 2023-09-30 12:45:43 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ;
cs int N = 5e5 + 5;
cs int mod = 1e9 + 7, g = 5;
int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
int mul(int a, int b) {
return 1ll * a * b % mod;
}
int dec(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
void Add(int &a, int b) {
a = add(a, b);
}
void Dec(int &a, int b) {
a = dec(a, b);
}
void Mul(int &a, int b) {
a = mul(a, b);
}
int ksm(int a, int b) {
int c = 1;
for(; b; b >>= 1, Mul(a, a))
if(b & 1) Mul(c, a);
return c;
}
int B = 3e6;
int n, k, G;
int p[N];
int E[N];
int A[N];
unordered_map <int, int> mp(B * 2);
int init(int m) {
int cur = 1;
for(int i = 0; i < m; i++) {
mp[cur] = i;
cur = mul(cur, g);
} return cur;
}
int getid(int x) {
// g ^ id = x
int cur = x;
int id = 0;
while(1) {
// cur = x * g ^ id
if(mp.count(cur)) {
int c = mp[cur];
// x * g ^ id = g ^ c
// x = g ^ {c - id}
return (c - id + mod - 1) % (mod - 1);
}
// cout << "FFFF " << cur << endl;
Mul(cur, G);
id = id + B;
}
}
void exgcd(ll a, ll b, ll & x, ll & y) {
if(!b) return x = 1, y = 0, void();
exgcd(b, a % b, y, x), y -= a / b * x;
}
int sqrtk(int x) {
if(x == 0) return 0;
int c = getid(x);
// cout << "ID " << x << " " << c << endl;
// assert(ksm(g, c) == x);
// X * k + Y (mod - 1) = c
// gcd(k, mod - 1) = 1
ll X = 0, Y = 0;
exgcd(k, mod - 1, X, Y);
Y = Y * c;
Y = (Y % k + k) % k;
ll ans = (c + Y * (mod - 1)) / k;
// assert(ksm(ksm(g, ans), k) == x);
return ksm(g, ans);
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
cin >> n >> k;
G = init(B);
// cout << G << endl;
for(int i = 2; i <= n; i++)
scanf("%d", &p[i]);
for(int i = 1; i <= n; i++)
scanf("%d", &E[i]);
for(int i = n; i > 1; i--)
Add(E[p[i]], E[i]);
vector <int> sm (n + 1);
for(int i = n; i; i--) {
int x = mul(n, sqrtk(E[i]));
Add(A[i], x);
Dec(A[p[i]], x);
// cout << "FFFF " << i <<' ' << E[i] << ' ' << A[i] << ' ' << x << ' ' << sqrtk(E[i]) << ' ' << n << endl;
}
cout << A[1] << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 333ms
memory: 151528kb
input:
2 1 1 2 1
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 346ms
memory: 149428kb
input:
1 1 2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 591ms
memory: 151916kb
input:
35224 611178003 1 2 1 4 4 4 6 7 4 2 8 1 7 7 10 1 15 9 8 19 4 11 1 1 1 21 18 1 29 13 22 14 28 2 34 15 29 32 36 15 23 15 15 30 19 2 27 36 42 7 12 41 47 19 8 48 22 58 47 46 33 60 62 55 65 25 39 37 64 65 51 5 62 32 52 54 23 47 71 48 12 57 66 14 21 67 51 48 63 4 61 6 40 91 79 76 75 51 83 22 22 65 30 2 99...
output:
633802282
result:
wrong answer 1st numbers differ - expected: '382077724', found: '633802282'