QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234544#7644. Good Splits275307894aWA 49ms7760kbC++141.5kb2023-11-01 19:04:402023-11-01 19:04:40

Judging History

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

  • [2023-11-01 19:04:40]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:7760kb
  • [2023-11-01 19:04:40]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e2+5,M=N*120+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,p;
ll f[N],g[N][N],C[N][N],ctl[N],dp[N][N],ans[N],ff[N];
void Solve(){
	int i,j,h;scanf("%d%d",&n,&p);
	for(i=0;i<=2*n;i++) for(C[i][0]=j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	ctl[0]=1;for(i=1;i<=n;i++) for(j=0;j<i;j++) ctl[i]=(ctl[i]+ctl[j]*ctl[i-j-1])%p;
	for(i=2;i<=2*n;i++){
		for(j=0;2*j<=i;j++) ans[i]+=C[i][2*j]*ctl[j]%p*ctl[i/2-j]%p;
		ans[i]%=p;
	}
	g[0][0]=dp[0][0]=1;
	for(i=1;i<=2*n;i++){
		for(j=1;j<=i;j++) g[i][j]=g[i-1][j-1],dp[i][j]=dp[i-1][j-1];
		for(j=1;j<=i;j++){
			for(h=1;2*h+1<=i;h++){
				g[i][j]=(g[i][j]+ans[h*2]*g[i-2*h-1][j-1])%p;
				dp[i][j]=(dp[i][j]+f[h*2]*dp[i-2*h-1][j-1])%p;	
			}
		}
		if(i%2==0){
			f[i]=ans[i];
			for(j=2;j<i;j+=2) f[i]-=g[i][j]*ff[j]*2%p;
			f[i]=(f[i]%p+p)*(p+1)/2%p;ff[i]=f[i];
			for(j=2;j<i;j+=2) f[i]+=dp[i][j]*ff[j]%p;
			printf("%lld\n",f[i]%p);
		}
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

详细

Test #1:

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

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

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

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

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

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

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
Wrong Answer
time: 49ms
memory: 7760kb

input:

177 861641813

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
51986430
817568411
233712834
530886113
262319436
602763301
391560421
714952237
234059952
504165773
214901044
343336951
654631331
578657419
506328910
26764748
407306588
36662800
819329882
372916107
103054885
512356475
207029843
192047130
1038...

result:

wrong answer 37th numbers differ - expected: '624069960', found: '286766099'