QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696393#4007. 树propane100 ✓340ms5696kbC++201.1kb2024-10-31 22:23:542024-10-31 22:23:54

Judging History

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

  • [2024-10-31 22:23:54]
  • 评测
  • 测评结果:100
  • 用时:340ms
  • 内存:5696kb
  • [2024-10-31 22:23:54]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
int n, mod;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int dp[505][505], ndp[505][505];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> mod;
    for(int i = 1; i <= n; i++) dp[1][i] = i;
    // dp[j][k] : 树1/2的非叶子结点数为j, k
    for(int i = 2; i <= n; i++){
        int ans = 0;
        for(int j = 1; j <= i; j++) add(ans, mul(dp[j][1], j));
        cout << ans << '\n';
        memset(ndp, 0, sizeof ndp);
        for(int j = 1; j <= i; j++){
            for(int k = 1; k <= n - i + 1; k++){
                add(ndp[j + 1][k], 1LL * dp[j][k] * j * k % mod);
                add(ndp[j][k], LL(mod - 2) * dp[j][k] % mod * j * k % mod);
                add(ndp[j][k - 1], 1LL * dp[j][k] * j * (k - 1) % mod);
            }
        }
        swap(dp, ndp);
    }

}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 5560kb

input:

10 577151064

output:

1
2
12
120
1928
44368
1394944
57288704
94480200

result:

ok 9 numbers

Test #2:

score: 10
Accepted
time: 5ms
memory: 5688kb

input:

20 993244853

output:

1
2
12
120
1928
44368
1394944
57288704
500961
765914688
721727386
828519746
578809878
456780398
566346177
528608756
112517275
556697045
568491469

result:

ok 19 numbers

Test #3:

score: 10
Accepted
time: 7ms
memory: 5580kb

input:

48 693389412

output:

1
2
12
120
1928
44368
1394944
57288704
206677872
93448752
311229980
378398080
125171140
600238484
463296372
561311928
329571716
372970120
613153144
269319584
39317988
650402652
168384404
534851656
34323712
215031272
571825440
276426924
452666204
65470204
266586376
160926452
211220340
374251752
67686...

result:

ok 47 numbers

Test #4:

score: 10
Accepted
time: 11ms
memory: 5640kb

input:

50 1000000021

output:

1
2
12
120
1928
44368
1394944
57288704
980235478
468922453
461761187
992820728
222191705
300367066
987453727
296887978
372555015
955448207
763668619
979367361
619326086
386572917
557116733
365169253
648460492
571297313
590441681
957006239
722930829
488988561
87845027
317417171
474978324
228338990
66...

result:

ok 49 numbers

Test #5:

score: 10
Accepted
time: 22ms
memory: 5568kb

input:

97 192608170

output:

1
2
12
120
1928
44368
1394944
57288704
91112970
16405484
80100176
70225008
48127872
176500510
39558398
22009052
21398644
141840316
189415170
192276316
116361256
72578142
52819502
188156950
188410248
176509638
32522564
83818754
28928230
65470204
73978206
122404818
134177072
66078680
21994318
88253492...

result:

ok 96 numbers

Test #6:

score: 10
Accepted
time: 19ms
memory: 5696kb

input:

100 949494599

output:

1
2
12
120
1928
44368
1394944
57288704
131751723
620512065
437266937
358823802
539191611
176844929
543845036
668141281
801642858
243456188
475342903
130532838
725579466
483897130
428695490
554394226
640052996
822143891
597926520
115217926
933551207
829213453
163959314
857759387
609179400
110139502
2...

result:

ok 99 numbers

Test #7:

score: 10
Accepted
time: 339ms
memory: 5572kb

input:

497 1000000008

output:

1
2
12
120
1928
44368
1394944
57288704
980235504
468924936
461954744
10738360
169104280
683889128
729152376
260582112
579791480
979908304
54091792
859511360
218597448
706142496
963545672
872576584
795238216
742370576
97990344
903219288
323919296
630916264
620417560
260644760
296622888
919475496
1351...

result:

ok 496 numbers

Test #8:

score: 10
Accepted
time: 340ms
memory: 5652kb

input:

500 100000007

output:

1
2
12
120
1928
44368
1394944
57288704
80235317
68913066
61031598
25284945
83829366
93302789
23195091
38492081
50524333
45168633
38292434
94285811
38365623
95982662
36801914
61735054
86235593
37972035
84765574
17006323
9043467
77114223
34713566
69229620
79941112
8779017
72345539
90479258
69839002
49...

result:

ok 499 numbers

Test #9:

score: 10
Accepted
time: 339ms
memory: 5652kb

input:

500 996996996

output:

1
2
12
120
1928
44368
1394944
57288704
986241528
45503232
308935592
470590336
414864760
435663620
961356588
861801516
878901872
769566388
645880240
288459596
396098292
38002044
7683212
214317124
691055404
806441252
62125056
689603568
150044048
690550336
767023528
962388620
234709476
688741452
634303...

result:

ok 499 numbers

Test #10:

score: 10
Accepted
time: 335ms
memory: 5624kb

input:

500 1000000009

output:

1
2
12
120
1928
44368
1394944
57288704
980235502
468924745
461939855
9360079
19341771
808233360
364373546
411824196
637521641
722309870
778158561
500366017
204013945
366241252
504956853
971244083
263757822
671356722
954932924
63228980
314686787
611190004
716522667
145587103
747614824
444047280
94915...

result:

ok 499 numbers

Extra Test:

score: 0
Extra Test Passed