QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191975#6125. Lucky Stars Managementucup-team1209#RE 1398ms245804kbC++202.7kb2023-09-30 13:06:552023-09-30 13:06:55

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 13:06:55]
  • 评测
  • 测评结果:RE
  • 用时:1398ms
  • 内存:245804kb
  • [2023-09-30 13:06:55]
  • 提交

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; 
} 

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: