QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191975 | #6125. Lucky Stars Management | ucup-team1209# | RE | 1398ms | 245804kb | C++20 | 2.7kb | 2023-09-30 13:06:55 | 2023-09-30 13:06:55 |
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 = 5e6;
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);
X = (X * c % (mod - 1) + mod - 1) % (mod - 1);
Y = Y * c;
Y = (-Y % k + k) % k;
ll ans = (c + Y * (mod - 1)) / k;
// cout << X << ' ' << ans << endl;
assert(ksm(ksm(g, X), k) == x);
assert(ksm(ksm(g, ans), k) == x);
return ksm(g, ans);
}
mt19937_64 rnd(time(0));
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]);
// for(int i = 0; i < 1e5; i++) {
// int x = rnd() % mod;
// assert(ksm(sqrtk(x), k) == x);
// }
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: 627ms
memory: 242404kb
input:
2 1 1 2 1
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 613ms
memory: 242808kb
input:
1 1 2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 804ms
memory: 244964kb
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:
382077724
result:
ok 1 number(s): "382077724"
Test #4:
score: 0
Accepted
time: 1398ms
memory: 245804kb
input:
149791 34987949 1 1 2 4 5 1 6 8 4 9 7 10 11 14 15 16 17 18 10 19 15 15 21 19 8 7 24 28 11 29 31 32 21 15 33 3 32 36 35 10 39 42 8 29 13 43 47 48 49 44 50 40 8 52 55 56 43 50 31 57 61 62 1 43 63 11 66 68 69 50 70 68 72 74 75 22 76 78 79 54 80 82 83 72 84 54 1 86 7 89 20 78 91 94 59 95 97 98 99 100 10...
output:
49310952
result:
ok 1 number(s): "49310952"
Test #5:
score: 0
Accepted
time: 1226ms
memory: 245800kb
input:
118590 920049643 1 1 2 1 4 6 1 7 7 10 9 1 4 10 13 10 17 18 17 10 19 22 15 22 25 23 26 28 17 29 3 26 19 31 2 14 4 35 39 40 41 37 18 42 20 45 27 9 46 1 30 47 44 29 47 27 53 26 58 1 60 62 14 51 6 28 63 68 43 69 71 10 27 2 72 76 77 76 78 50 81 40 79 25 81 50 80 54 14 5 88 91 92 94 95 96 97 93 17 62 36 2...
output:
657262978
result:
ok 1 number(s): "657262978"
Test #6:
score: 0
Accepted
time: 1272ms
memory: 243844kb
input:
124407 288831131 1 2 2 3 5 6 5 3 7 10 6 1 2 11 15 1 17 3 16 20 14 18 21 23 18 17 13 24 29 30 31 6 17 32 35 36 37 17 22 38 41 2 42 44 34 15 45 25 39 49 12 45 48 28 54 56 57 33 58 60 22 61 63 64 65 22 66 68 25 1 69 72 31 65 32 47 4 73 79 30 80 82 83 84 85 58 86 36 88 90 37 91 88 89 17 93 97 31 56 98 7...
output:
948978942
result:
ok 1 number(s): "948978942"
Test #7:
score: 0
Accepted
time: 975ms
memory: 245168kb
input:
67899 312198691 1 1 1 2 1 6 7 5 2 7 11 12 13 13 15 16 16 18 19 20 12 21 23 15 24 10 6 26 29 30 31 32 33 34 32 16 24 5 35 40 41 28 15 32 42 46 47 47 49 50 46 51 46 47 53 56 38 23 56 19 11 58 11 55 57 60 1 40 53 67 71 61 72 1 74 76 64 77 27 79 49 19 81 84 34 85 46 76 87 90 83 91 93 41 94 96 9 77 84 97...
output:
402649812
result:
ok 1 number(s): "402649812"
Test #8:
score: 0
Accepted
time: 756ms
memory: 244696kb
input:
28006 754395459 1 2 3 3 5 6 7 8 5 6 9 12 13 3 14 1 4 16 3 19 13 21 23 21 19 24 4 27 9 29 16 31 33 8 18 34 2 27 34 28 37 35 42 44 45 46 47 48 49 17 50 52 29 53 37 32 55 58 53 59 61 23 62 64 65 66 67 6 68 70 50 5 40 1 71 76 77 5 26 30 78 82 32 78 83 86 87 72 66 47 88 92 50 93 95 32 96 98 99 34 17 7 28...
output:
460692207
result:
ok 1 number(s): "460692207"
Test #9:
score: -100
Runtime Error
input:
54784 500000003 1 1 1 2 1 1 7 3 6 4 2 6 8 12 6 9 13 9 12 8 7 12 11 8 10 24 17 14 8 19 15 27 32 6 30 24 29 37 21 29 26 5 32 2 13 9 35 12 40 45 47 2 19 34 32 10 57 55 7 58 8 26 4 10 60 38 52 65 30 23 70 65 46 11 31 40 40 22 41 50 61 44 57 10 35 61 19 15 87 64 50 49 2 34 95 12 37 9 6 58 8 33 21 64 73 6...