QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229275#7644. Good Splitsucup-team052#TL 1106ms31640kbC++141.2kb2023-10-28 15:38:162023-10-28 15:38:16

Judging History

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

  • [2023-10-28 15:38:16]
  • 评测
  • 测评结果:TL
  • 用时:1106ms
  • 内存:31640kb
  • [2023-10-28 15:38:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int md;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

const int N = 205;

int dp[N * 2][N][N], ans[N], ret[N];
int n;

inline void upd(int &x, int y) {
	x = add(x, y);
}

inline void dec(int &x, int y) {
	x = sub(x, y);
}

int main() {
	cin >> n >> md;
	dp[1][1][0] = 1;
	for (int i = 2; i <= n * 2; i++) {
		for (int j = 0; j <= min(n, i); j++) {
			for (int k = 0; k <= min(n, i) - j; k++) {
				upd(dp[i][j][k], dp[i - 1][j + 1][k]);
				upd(dp[i][j][k], dp[i - 1][j][k + 1]);
				if (j) upd(dp[i][j][k], dp[i - 1][j - 1][k]);
				if (k) upd(dp[i][j][k], dp[i - 1][j][k - 1]);
				for (int t = 1; t <= i / 2; t++) {
					dec(dp[i][j][k], mul(dp[i - t * 2][j][k], ret[t]));
				}
			}
		}
		if (i % 2 == 0) {
			ret[i / 2] = dp[i][0][0];
			dp[i][0][0] = 0;
		}
	}
	ans[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) upd(ans[i], mul(ans[j], ret[i - j]));
		cout << ans[i] << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3484kb

input:

5 998244353

output:

1
3
14
84
592

result:

ok 5 number(s): "1 3 14 84 592"

Test #2:

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

input:

20 998244353

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
503820623
71483496
12733593
474907036
203223726
565209211
487441118
992424798
625482036

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 4688kb

input:

30 147084737

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
43415138
115604731
88255570
6762644
25928144
117374310
119291296
29414136
87790057
136053957
103827626
145662835
60977924
8837626
61475022
108138661
88536961
105609125
140429327
77714436

result:

ok 30 numbers

Test #4:

score: 0
Accepted
time: 11ms
memory: 6772kb

input:

50 259851877

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
77732735
120479281
107558023
219154876
82657644
224090144
253190966
148874121
53920249
82785846
244357960
88406017
106161945
35184035
131007270
222579610
212725099
114435754
64242919
39323449
211238313
156440547
84150382
242052946
50634162
120017303
2...

result:

ok 50 numbers

Test #5:

score: 0
Accepted
time: 188ms
memory: 16248kb

input:

100 175127923

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
162456689
171123145
54532804
71333538
68283136
25628469
138841774
142350839
27676343
15931022
158187457
43201304
18465009
37939972
169592319
94983552
152752931
69017296
46403905
173424585
170947507
7870926
90491276
10182721
58907963
136216980
28163587...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 1106ms
memory: 31640kb

input:

150 367542041

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
190675313
252320457
264200037
124276323
161424010
184935571
230223063
343780965
314302578
342350468
265272499
173792750
339843799
301192856
263531782
208259173
113525686
44197147
288967350
139023077
142942582
324678736
318907769
315638511
40...

result:

ok 150 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

177 861641813

output:


result: