QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#57997#4836. TreeMIT01#TL 60ms22052kbC++1.6kb2022-10-24 08:12:462022-10-24 08:12:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-24 08:12:47]
  • 评测
  • 测评结果:TL
  • 用时:60ms
  • 内存:22052kb
  • [2022-10-24 08:12:46]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
using namespace std;
const int maxn = 505;
int dp[maxn][maxn][maxn]; // index, 
ll ans[maxn];
int n, mod;

int main() {
    cin >> n >> mod;
    for (int k = 0; k <= n; k++)
        dp[1][0][k] = k;
    for (int i = 1; i < n; i++)
        for (int l = 0; l <= i; l++)
            for (int g = 0; g <= n; g++) {
               // if (dp[i][l][g]) cout << i << " " << l << " " << g << " " << dp[i][l][g] << endl;
                for (int tp = 0; tp < 4; tp++) {
                    if (tp == 0) continue;

                    int eg = g; 
                    if (!(tp & 2)) 
                        eg -= 1; // down not leaf

                    if (eg <= 0) continue;
                    ll cont = 1ll * (i - l) * dp[i][l][g] % mod * eg % mod;

                    int el = l;
                    if ((tp & 1)) el += 1;
                    if (tp == 3) cont *= -2, cont %= mod;
                    dp[i + 1][el][eg] = (dp[i + 1][el][eg] + cont) % mod;
                }
            }
    for (int i = 1; i <= n; i++)
        for (int k = 0; k <= i; k++) 
            ans[i + 1] = (ans[i + 1] + 1ll * dp[i][k][1] * (i - k)) % mod;
    for (int i = 2; i <= n; i++) {
        int res = ans[i];
        res %= mod;
        if (res < 0) res += mod;
        cout << res << endl;
    }
    return 0;

}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7784kb

input:

5 998244353

output:

1
2
12
120

result:

ok 4 number(s): "1 2 12 120"

Test #2:

score: 0
Accepted
time: 5ms
memory: 14360kb

input:

50 10007

output:

1
2
12
120
1928
4340
3971
8636
815
1971
1138
4657
4784
7523
951
6104
2967
9876
5030
4921
4936
8826
5951
3506
1431
7190
8667
655
5143
4548
1416
7845
3569
4220
8273
2745
1650
7824
8477
3716
366
9885
5166
7416
6843
1214
7262
3538
681

result:

ok 49 numbers

Test #3:

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

input:

10 577151064

output:

1
2
12
120
1928
44368
1394944
57288704
94480200

result:

ok 9 numbers

Test #4:

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

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 #5:

score: 0
Accepted
time: 5ms
memory: 14248kb

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 #6:

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

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 #7:

score: 0
Accepted
time: 60ms
memory: 21596kb

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 #8:

score: 0
Accepted
time: 56ms
memory: 22052kb

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 #9:

score: -100
Time Limit Exceeded

input:

497 1000000008

output:


result: