QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#57957#4836. TreeSorting#TL 60ms6196kbC++971b2022-10-23 23:09:232022-10-23 23:09:24

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-23 23:09:24]
  • 评测
  • 测评结果:TL
  • 用时:60ms
  • 内存:6196kb
  • [2022-10-23 23:09:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll mod;
ll n;
ll dp[2][501][501];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> mod;
	for(int i=0; i<=n ;i++){
		dp[0][0][i]=mod-1;
		dp[0][1][i]=1;
	}
	for(int r=1; r<n ;r++){
		int c=r%2;
		int p=c^1;
		for(int i=0; i<=n ;i++){
			for(int j=0; j<=n ;j++){
				dp[p][i][j]=dp[p][i][j]*i*j%mod;
				dp[c][i][j]=0;
			}
		}
		{//use x
			for(int i=0; i<=n ;i++){
				for(int j=0; j<=n ;j++){
					dp[c][i][j]=(dp[c][i][j]+mod-dp[p][i][j])%mod;
					if(i<n) dp[c][i+1][j]=(dp[c][i+1][j]+dp[p][i][j])%mod;
				}
			}
		}
		{//use y
			for(int i=0; i<=n ;i++){
				for(int j=0; j<=n ;j++){
					dp[c][i][j]=(dp[c][i][j]+mod-dp[p][i][j])%mod;
					if(j>0) dp[c][i][j-1]=(dp[c][i][j-1]+dp[p][i][j])%mod;
				}
			}
		}
		ll ans=0;
		for(int j=0; j<=n ;j++) ans=(ans+dp[c][j][0])%mod;
		cout << ans << '\n';
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5632kb

input:

5 998244353

output:

1
2
12
120

result:

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

Test #2:

score: 0
Accepted
time: 7ms
memory: 5752kb

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: 3752kb

input:

10 577151064

output:

1
2
12
120
1928
44368
1394944
57288704
94480200

result:

ok 9 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 5736kb

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: 6ms
memory: 5852kb

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: 7ms
memory: 3932kb

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: 6196kb

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: 41ms
memory: 6040kb

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: