QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191940#6125. Lucky Stars Managementucup-team1209#WA 591ms151916kbC++202.5kb2023-09-30 12:45:422023-09-30 12:45:43

Judging History

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

  • [2023-09-30 12:45:43]
  • 评测
  • 测评结果:WA
  • 用时:591ms
  • 内存:151916kb
  • [2023-09-30 12:45:42]
  • 提交

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'