QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#421641#5402. 术树数Crying20 860ms19640kbC++142.5kb2024-05-25 23:23:082024-05-25 23:23:08

Judging History

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

  • [2024-05-25 23:23:08]
  • 评测
  • 测评结果:20
  • 用时:860ms
  • 内存:19640kb
  • [2024-05-25 23:23:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10,M = 30;
int q,k,m,n;

int dep[MAXN],dis[MAXN],fa[20][MAXN];

namespace Num{
    int p[M],q[M];
    void fac(int n,int* p){ for(int x=1;x<=m;x++)p[x]=n%k,n/=k;}
    int rfac(int* p){int num = 0; for(int i=M;i>=1;i--)num = num*k + p[i]; return num; }
    int add(int a,int b){
        fac(a,p); fac(b,q); 
        for(int i=1;i<=m;i++)p[i] = (p[i]+q[i])%k;
        return rfac(p);
    }
    int mul(int a,int b){
        fac(a,p);
        for(int i=1;i<=m;i++)p[i] = 1ll*p[i]*b%k;
        return rfac(p);
    }
    //
    int a[M][M],tmp[M];
    void exgcd(int* p,int* q,int x){
        if(!q[x])return;
        int d = p[x]/q[x];
        for(int i=x;i>=1;i--)p[i] = ((p[i]-1ll*q[i]*d)%k+k)%k;
        exgcd(q,p,x);
    }
    void ins(int n){
        fac(n,tmp);
        for(int i=m;i>=1;i--)if(tmp[i]){
            exgcd(a[i],tmp,i); 
            if(!a[i][i])for(int j=1;j<=m;j++)swap(a[i][j],tmp[j]);
        }
    }
    void qry(int w){
        fac(w,tmp); 
        //printf("qry %d\n",w);
        for(int i=m;i>=1;i--)if(a[i][i]){
            int g = __gcd(a[i][i],k),r = a[i][i]%g;
            int to = (tmp[i]+r)%g,d = 0;
            while((tmp[i]+1ll*d*a[i][i])%k != to)d++;
            for(int j=i;j>=1;j--)tmp[j] = (tmp[j]+1ll*a[i][j]*d)%k;
        }
        w = rfac(tmp); cout<<w<<"\n";
    }
}; using Num::add; using Num::mul; using Num::ins; using Num::qry;

int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(int j=19;j--;)if(dep[x]-(1<<j) >= dep[y])x = fa[j][x];
    if(x==y)return x;
    for(int j=19;j--;)if(fa[j][x] != fa[j][y])x = fa[j][x],y = fa[j][y];
    return fa[0][x];
}

int W(int x,int y){
    int p = lca(x,y); 
    return add(add(dis[x],dis[y]),mul(dis[p],2*(k-1)));
}

int main(){
    //freopen("city.in","r",stdin); freopen("city.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>q>>k>>m; n = 1;

    for(int o,x,y,v;q--;){
        cin>>o;
        if(o==1){
            cin>>x>>v;
            n++; dis[n] = add(dis[x],v),dep[n] = dep[x] + 1,fa[0][n] = x;
            for(int j=1;j<20;j++)fa[j][n] = fa[j-1][fa[j-1][n]];

            v = mul(v,2);
            //printf("ins %d\n",v);
            ins(v);
        }else if(o==2){
            cin>>x>>y>>v;
            int w = add(W(x,y),v); 
            
            ins(w);
        }else{
            cin>>x>>y;

            int w = W(x,y); 
            qry(w);
            //exit(0);
        }
    }

    return 0;
}

詳細信息

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 0ms
memory: 18072kb

input:

30 7 3
1 1 301
1 1 236
1 2 278
3 2 4
3 2 4
2 1 4 265
1 1 242
1 4 278
1 6 337
3 2 3
2 5 7 304
2 5 6 34
1 4 178
3 6 7
3 5 7
3 1 4
1 1 178
3 3 4
3 1 6
3 3 4
2 6 7 131
1 1 213
3 1 3
2 3 10 11
3 4 6
2 5 9 169
1 6 9
2 5 10 29
1 9 111
3 9 11

output:

0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 12 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 15964kb

input:

30 9 3
1 1 694
1 2 251
1 2 623
2 2 4 109
3 3 4
3 1 2
2 2 4 611
1 4 595
2 2 5 477
2 2 5 363
3 1 3
2 1 5 121
1 2 225
2 1 5 214
2 3 6 706
3 3 4
2 2 3 122
2 2 3 621
3 2 3
3 2 4
2 1 5 630
1 5 598
3 4 5
3 1 3
1 2 665
2 1 2 331
2 1 6 449
1 2 387
3 3 6
3 4 6

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 18024kb

input:

30 4 5
1 1 854
1 1 467
1 2 708
2 2 4 529
1 4 115
1 4 444
2 3 4 108
2 2 5 724
2 1 3 375
1 5 827
2 5 6 974
1 3 73
3 2 3
2 2 3 140
3 5 6
2 6 8 787
3 1 5
1 5 971
3 4 6
2 4 5 816
3 7 8
3 2 4
1 6 855
2 5 10 39
2 6 9 280
2 6 10 662
3 7 10
1 6 412
3 4 7
1 6 276

output:

0
256
256
256
0
0
0
0

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 15912kb

input:

30 6 4
1 1 1246
1 1 825
1 3 843
2 1 3 186
2 2 3 228
2 1 3 1187
3 2 3
3 1 4
1 3 942
3 1 2
1 5 779
2 3 4 775
2 1 2 275
2 1 3 309
2 5 6 1175
3 2 6
1 6 1084
3 4 6
1 7 176
3 5 6
2 3 8 431
3 2 6
3 1 4
1 8 725
3 7 9
3 1 4
3 6 7
3 2 4
3 1 6
1 5 972

output:

1
6
7
0
0
0
0
0
0
0
0
0
0

result:

ok 13 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 17956kb

input:

30 6 4
1 1 1050
1 2 312
1 3 665
2 1 4 49
2 1 3 394
2 3 4 1225
3 1 4
1 1 381
3 1 2
1 3 933
1 3 551
2 2 6 521
3 3 5
2 2 6 1219
3 3 7
1 6 953
1 3 403
2 1 7 624
1 8 981
3 1 2
1 9 1052
2 4 9 971
2 5 8 575
3 1 7
2 6 9 953
2 1 10 347
3 3 11
2 3 9 878
1 6 991
2 6 11 681

output:

1
0
1
1
0
0
0

result:

ok 7 lines

Test #6:

score: 0
Accepted
time: 2ms
memory: 18012kb

input:

30 4 5
1 1 48
1 2 924
1 2 587
3 3 4
2 1 3 63
1 1 600
2 2 5 747
1 5 252
2 2 5 777
2 2 3 119
1 3 914
1 1 708
2 2 3 670
2 3 5 526
3 3 7
1 5 816
1 9 401
1 2 364
2 7 10 16
2 10 11 254
1 6 641
1 10 406
2 6 10 324
1 5 29
1 12 493
2 3 15 125
1 12 95
1 4 370
2 8 16 766
1 11 307

output:

341
0

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 15904kb

input:

30 3 6
1 1 358
1 2 16
1 1 636
1 1 156
1 4 512
3 3 4
3 5 6
3 1 2
2 2 5 271
3 4 6
2 3 5 5
1 2 566
3 3 4
3 4 6
3 2 3
2 4 6 472
2 2 6 119
1 1 260
2 1 8 488
1 7 345
1 8 368
2 6 9 649
1 1 553
2 1 9 416
3 8 9
1 10 630
1 9 156
1 3 14
1 4 407
3 4 10

output:

0
0
0
0
0
0
0
0
0

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 17952kb

input:

3 8 3
1 1 401
1 2 0
3 1 2

output:

179

result:

ok single line: '179'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 17956kb

input:

996 4 8
1 1 43515
1 1 674
1 1 0
3 3 4
1 3 26873
3 3 5
3 3 4
1 2 0
1 5 26201
1 7 0
3 1 3
3 2 6
1 2 2722
1 4 674
1 10 35328
3 3 5
1 2 2048
3 10 11
2 2 8 34808
3 10 11
3 1 4
3 3 11
3 3 7
3 1 2
1 2 10753
3 12 13
3 3 4
1 12 32928
3 9 13
3 3 8
2 3 10 3
3 5 8
1 9 34978
1 13 2722
3 8 14
3 2 3
1 9 43681
3 7 ...

output:

0
26873
0
0
0
24825
0
0
0
0
1026
506
0
0
0
1024
17496
1528
504
1528
16640
504
1024
1528
1528
16640
16472
16640
16472
0
0
504
504
504
0
16640
1024
504
504
504
0
0
504
0
504
16640
0
504
0
504
16640
16640
16640
0
0
0
0
0
504
0
0
16472
0
0
1024
1024
504
504
0
504
0
16640
504
0
0
0
504
16640
0
0
504
504
...

result:

wrong answer 11th lines differ - expected: '1024', found: '1026'

Subtask #3:

score: 0
Time Limit Exceeded

Test #21:

score: 11
Accepted
time: 279ms
memory: 19384kb

input:

198517 3 16
1 1 40710744
1 2 21885097
1 1 23592366
1 4 7387074
1 5 16074177
1 1 41027400
1 4 18082971
1 2 12822448
1 1 2286557
1 1 27896295
1 11 14532760
1 8 2357296
1 11 9190559
1 6 40503152
3 4 11
3 1 7
3 3 7
3 8 14
3 12 15
3 2 3
1 10 34606866
1 13 42718465
1 16 30353561
3 5 11
3 2 6
3 16 18
1 3 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99662 lines

Test #22:

score: 0
Accepted
time: 156ms
memory: 18356kb

input:

198073 8 8
1 1 4007183
1 1 411647
1 1 3301064
1 1 2747675
1 3 11141272
1 3 4308435
1 4 15582931
1 5 11340890
1 2 9172283
1 9 542280
1 10 12209796
1 3 2829956
3 1 3
1 3 724504
3 2 14
3 3 14
3 9 12
3 7 10
1 1 3594204
1 14 13600647
1 15 4589767
3 10 14
1 4 10564184
1 13 1781174
1 19 6067505
1 9 6735060...

output:

262729
2097224
520
4673
2097672
2134081
2101769
2134080
2101832
2130432
584
2129992
2392584
2134024
2101824
2363904
295424
36864
4608
0
295489
299593
1
33353
2359305
2130440
2130497
2363969
4161
294976
37440
2359361
299080
2101248
299592
33344
2392576
2359816
2097160
8
2359880
262657
2101832
2363464...

result:

ok 99445 lines

Test #23:

score: 0
Accepted
time: 121ms
memory: 19452kb

input:

198343 50 4
1 1 4597949
1 1 1140260
1 1 1078946
1 3 4494430
1 4 3030702
1 5 5215333
1 4 5366961
1 2 4836213
1 5 3721812
1 1 486900
1 3 2631122
3 7 11
1 1 384111
3 6 10
3 1 3
1 1 6239546
3 6 10
1 5 4354709
3 11 12
3 6 13
1 9 863486
1 15 5296752
1 12 1997611
3 15 16
1 11 6087993
3 1 13
1 9 4926906
3 1...

output:

2551
125050
125050
125050
125050
125001
1
127501
127550
125050
125000
2500
2550
125000
125001
50
50
51
50
127550
127501
2500
125000
50
127500
2550
125000
50
127500
125051
1
2550
127551
51
127501
1
127551
2500
125000
2551
2551
125000
127501
1
50
51
2551
2550
125001
0
2500
125001
2500
50
127500
125001...

result:

ok 99620 lines

Test #24:

score: 0
Accepted
time: 860ms
memory: 19640kb

input:

199495 2675 2
1 1 6874452
1 1 2927709
1 1 4714827
1 1 341697
1 1 5807384
1 2 6029400
1 6 3410507
1 1 4255734
1 9 7116423
1 3 5647617
3 5 11
1 5 2479935
3 9 10
3 2 6
1 4 6921813
1 12 4608236
1 11 932260
1 11 5347104
3 1 11
3 11 14
1 12 715746
3 8 17
1 14 1418580
1 3 6123273
1 4 6481423
1 1 4166639
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100058 lines

Test #25:

score: -11
Time Limit Exceeded

input:

199531 45237947 1
1 1 15260546
1 1 30197693
1 2 3455446
1 1 29660068
1 5 5406610
1 2 32468080
1 6 33471078
1 7 3670881
1 7 11684247
1 7 8493599
1 1 4296342
3 5 6
1 9 41359920
3 2 11
1 4 37376116
3 2 5
1 9 44209222
3 2 14
1 13 11322652
3 11 13
1 7 3505613
1 14 30321158
1 3 3184527
1 11 14996243
1 19 ...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #26:

score: 0
Time Limit Exceeded

input:

198891 26426880 1
1 1 0
2 1 2 0
3 1 2
1 1 0
3 2 3
3 1 2
1 2 0
1 2 0
1 3 0
1 6 0
2 1 6 0
2 3 6 0
3 2 3
1 2 13213440
1 2 13213440
1 4 13213440
3 4 10
1 1 13213440
2 3 4 0
2 3 8 13213440
1 1 0
1 12 0
1 13 0
1 3 0
3 2 11
3 2 12
2 11 14 13213440
1 6 0
2 12 14 0
2 1 2 0
1 10 0
1 12 0
2 3 13 0
3 12 14
3 1 ...

output:

0
0
0
0
13213440
13213440
0
0
0
13213440
0
0
13213440
0
13213440
0
13213440
0
13213440
13213440
13213440
13213440
13213440
0
13213440
13213440
0
13213440
13213440
0
0
0
13213440
0
13213440
0
13213440
0
0
0
13213440
13213440
0
13213440
13213440
13213440
13213440
0
13213440
13213440
13213440
13213440
...

result:


Subtask #5:

score: 15
Accepted

Test #30:

score: 15
Accepted
time: 303ms
memory: 18964kb

input:

199458 2 25
1 1 31252443
2 1 2 22827339
1 2 13517756
1 2 5635412
1 3 33397078
1 3 33542998
2 3 5 1484991
3 5 6
2 1 3 7938846
2 1 2 3665458
1 3 29150948
3 4 5
1 3 733545
1 7 4698781
1 7 21699192
1 6 10854390
3 3 8
3 4 8
1 2 6889338
2 1 12 27646676
2 6 8 24407215
1 11 20847453
3 4 13
1 6 16891344
3 4 ...

output:

150016
891079
733545
1048849
7306736
7012
6336311
7310241
705870
794721
112806
777734
2522042
203310
370916
2339461
699806
747148
597151
969956
2633367
376785
884917
884917
331441
2696956
2423527
2304668
2457533
2783258
690228
864462
360811
124716
2098167
48248
2869827
605003
235881
2739062
2861794
...

result:

ok 66461 lines

Test #31:

score: 0
Accepted
time: 308ms
memory: 17688kb

input:

198986 2 25
1 1 11331234
1 2 24833898
2 1 3 10628416
3 2 3
1 3 6115878
2 2 4 23717273
1 3 18406568
2 2 4 1949969
1 4 6063130
1 6 25760596
3 1 2
3 5 7
3 5 6
3 2 6
3 1 7
1 6 31753825
3 1 4
2 3 4 6115878
3 2 6
2 3 5 22447229
3 1 3
2 3 4 6115878
2 4 7 1813362
3 2 4
2 1 8 8192320
3 3 5
1 7 114729
1 9 188...

output:

969698
11331234
9443776
2324169
990686
1086581
11610035
990686
10628416
1949969
2269429
1949969
571284
3254790
682010
502346
824812
623366
377762
377762
2376509
884877
2316090
2244147
665245
341785
922389
928237
744294
69811
404242
789948
620664
513259
317968
222762
169970
969698
12365
1046658
91964...

result:

ok 65927 lines

Test #32:

score: 0
Accepted
time: 303ms
memory: 17676kb

input:

198119 2 25
1 1 1988220
2 1 2 10935842
2 1 2 10935842
3 1 2
1 2 9175257
2 1 2 30426983
1 3 21520990
1 2 7244347
2 3 5 19700729
1 3 24753647
3 4 6
2 1 2 30426983
3 2 4
1 6 25686082
2 1 6 22244116
1 7 20608501
3 3 6
1 2 29561714
2 2 3 21107138
1 1 21122181
1 6 7460982
2 7 9 19503627
1 9 8058976
3 1 8
...

output:

1988220
3266481
684956
994474
48107
1167209
4443137
4685362
1360512
4639448
238700
348592
278885
295451
489693
344667
180320
328346
407326
454344
485048
139415
148539
301162
209675
136220
454344
201497
48475
346271
411773
397728
487925
400145
418154
120548
273314
523155
476405
141994
243836
128983
7...

result:

ok 65949 lines

Subtask #6:

score: 3
Accepted

Test #33:

score: 3
Accepted
time: 72ms
memory: 18216kb

input:

49958 1023 2
1 1 122428
1 1 917186
2 2 3 53148
1 3 876461
2 1 3 968146
2 2 4 569341
2 3 4 199413
2 1 4 238371
1 3 127427
1 2 887225
2 1 4 776059
2 4 6 155479
2 1 6 795533
1 5 159578
3 5 6
2 2 5 758778
2 5 6 601115
3 4 7
1 4 202224
2 5 6 902346
3 1 6
3 5 7
3 3 5
1 2 791251
1 5 502214
2 6 7 929048
1 6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 16607 lines

Test #34:

score: 0
Accepted
time: 198ms
memory: 17764kb

input:

198392 7 9
1 1 23598910
3 1 2
1 1 25616681
2 1 2 22101090
2 2 3 25455751
3 1 2
3 1 2
1 3 25668120
3 1 3
1 3 23878180
1 4 10885281
1 1 5873751
2 2 7 31608236
3 2 3
3 3 5
2 2 6 37313936
2 1 6 36853293
2 4 7 6773989
2 1 7 19143946
3 2 7
3 3 7
3 1 2
1 1 31756932
3 3 6
2 5 8 39585364
1 2 27162269
3 4 5
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 65758 lines

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%