QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377632#6196. Minimum Element Problem275307894aAC ✓169ms60032kbC++143.1kb2024-04-05 16:09:102024-04-05 16:09:11

Judging History

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

  • [2024-04-05 16:09:11]
  • 评测
  • 测评结果:AC
  • 用时:169ms
  • 内存:60032kb
  • [2024-04-05 16:09:10]
  • 提交

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
#define all(x) x.begin(),x.end()
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>;
const int N=(1<<20)+5,M=(1<<20)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,x,k;ll A[N],B[N],frc[N],inv[N];
ll mpow(ll x,int y=mod-2){ll ans=1;while(y) y&1&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;}
namespace poly{
	int tr[N];ll pw[N];const int g=3;
	void init(int n){
		for(k=2;k<=n;k<<=1);
		for(int i=0;i<k;i++) tr[i]=(tr[i>>1]>>1)|(i&1?k/2:0);
		pw[k/2]=1;pw[k/2+1]=mpow(g,(mod-1)/k);
		for(int i=k/2+2;i<k;i++) pw[i]=pw[i-1]*pw[k/2+1]%mod;
		for(int i=k/2-1;i;i--) pw[i]=pw[i<<1];
	}
	void ntt(ll *A,int k,int flag){
		static ull a[N];for(int i=0;i<k;i++) a[tr[i]]=A[i];
		for(int i=2;i<=k;i<<=1){
			ll *e=pw+i/2;
			for(int j=0;j<k;j+=i) for(int h=j;h<j+i/2;h++){
				ull y=a[h+i/2]*e[h-j]%mod;
				a[h+i/2]=a[h]+mod-y;a[h]+=y;
			}
			if(i==(1<<18)){
				for(int j=0;j<k;j++) a[j]%=mod;
			}
		}
		for(int i=0;i<k;i++) A[i]=a[i]%mod;
		if(flag) return;
		reverse(A+1,A+k);
		ll iv=mpow(k);for(int i=0;i<k;i++) A[i]=A[i]*iv%mod;
	}
}
void mul(ll *A,ll *B){
	// static ll C[N];Me(C,0);
	poly::init(n+1);
	poly::ntt(A,k,1);poly::ntt(B,k,1);
	for(int i=0;i<k;i++) A[i]=A[i]*B[i]%mod;
	poly::ntt(A,k,0);
	// for(int i=0;i<=n;i++) for(int j=0;i+j<=n;j++) C[i+j]+=A[i]*B[j]%mod;
	// for(int i=0;i<=n;i++) A[i]=C[i]%mod;
}
ll ans[N],f[N],g[N];
ll C(int x,int y){return x>=y&&y>=0?frc[x]*inv[y]%mod*inv[x-y]%mod:0;}
ll calc(int x){return (C(2*x,x)-C(2*x,x+1)+mod)%mod;}
ll Go(int d,int n){
	int tx=2*n-(d+1),ty=d-1;
	return (C(tx,tx+ty>>1)-C(tx,tx+2*-1-ty>>1)+mod)%mod;
}
void Solve(){
	int i,j;scanf("%d%d",&n,&x);
	inv[1]=1;for(i=2;i<=2*n;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
	for(frc[0]=inv[0]=i=1;i<=2*n;i++) frc[i]=frc[i-1]*i%mod,inv[i]=inv[i-1]*inv[i]%mod;
	gdb(Go(2,1));
	for(i=1;i<=n;i++) f[i-1]=Go(i,x)*inv[i-1]%mod,g[i-1]=Go(i,n-x+1)*inv[i-1]%mod;
	mul(f,g);
	for(i=0;i<=n;i++) ans[i+1]+=f[i]*frc[i]%mod;
	Me(f,0);Me(g,0);
	for(i=0;i<x;i++) f[i]=calc(i);for(i=0;i<=n-x;i++) g[i]=calc(i);
	mul(f,g);
	for(i=0;i<=n;i++) ans[n-i+1]-=f[i]*calc(n-i-1)%mod;
	for(i=1;i<=n;i++) ans[i]=((ans[i-1]+ans[i])%mod+mod)%mod,printf("%lld\n",ans[i]);
}
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: 0ms
memory: 30524kb

input:

5 2

output:

5
10
16
20
14

result:

ok 5 number(s): "5 10 16 20 14"

Test #2:

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

input:

10 5

output:

588
1176
2716
4942
7407
9101
9636
9167
7596
4862

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 163ms
memory: 60032kb

input:

500000 1

output:

752527092
752527092
356448531
118361535
80175537
877228690
209078427
453506156
121930551
870611121
548521681
932222500
877888556
339507693
727002572
260384266
821810888
163642149
575555577
658980933
234580785
344625334
385680534
342084167
446322884
625631289
815673835
143033406
834945846
697825903
4...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 160ms
memory: 58464kb

input:

500000 233333

output:

138363804
276727608
913261867
200515458
98174965
678246093
927769485
382014114
279795571
189839383
793297320
457630387
247544984
428942831
277533813
88681322
624390630
921439292
168596569
954739113
979085346
687234058
393708687
497103558
286734849
179380498
473893314
393946995
822316346
485246191
92...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 148ms
memory: 57804kb

input:

499999 114514

output:

341241717
682483434
394686579
953386037
677673958
904444378
480913543
895868144
176048066
234816259
736395238
354978365
6204402
236101366
864038383
804451311
473145556
770789285
76089413
836469366
829878019
448657883
22407787
956778740
776897403
375485911
804351816
370141803
717651675
394600139
5347...

result:

ok 499999 numbers

Test #6:

score: 0
Accepted
time: 169ms
memory: 57936kb

input:

466047 378542

output:

316308363
632616726
625328547
548058021
467831491
412249015
562771998
508534419
702318310
663161493
71297932
569391807
528363739
577103129
75851585
281129409
253324073
555237826
523497876
9329476
595651189
113409967
689415978
758768684
461344695
271342234
922636023
896745521
753799440
454281460
8498...

result:

ok 466047 numbers

Test #7:

score: 0
Accepted
time: 147ms
memory: 58360kb

input:

497799 442442

output:

540969780
83695207
921588610
541249578
212472530
147071951
843635401
456883686
551483676
319785278
129435321
398101925
294235139
653012857
781822424
891809319
10513719
612056872
376014502
828906445
950887259
230704126
807999128
290793371
246195343
411365869
934684624
509617751
998233677
996675668
34...

result:

ok 497799 numbers

Test #8:

score: 0
Accepted
time: 150ms
memory: 57736kb

input:

466753 419673

output:

597092992
195941631
35282209
670914306
416494384
664725208
464875750
709887141
730156891
961628244
14612612
245382798
764095090
474984466
17211503
243033312
636210322
917825652
374184874
65295028
974019379
560137128
569803312
547566684
460710417
911778842
953566231
318861526
622281663
898785393
3283...

result:

ok 466753 numbers

Test #9:

score: 0
Accepted
time: 144ms
memory: 58064kb

input:

467106 241969

output:

604311529
210378705
653856122
53407242
877563744
89862040
632233611
996021679
619177538
520557738
575283710
211917888
496972337
34709258
595060683
625661602
15046904
770633381
497290822
218631007
239931201
23236894
578432596
428901738
504948079
877566897
998082459
443758906
296654733
59363332
898295...

result:

ok 467106 numbers

Test #10:

score: 0
Accepted
time: 155ms
memory: 58124kb

input:

486061 115034

output:

331165032
662330064
25375445
506130213
871487194
485340585
595821481
719592290
466027466
441948467
508478606
8931379
859094189
505253385
804451132
52690798
925691683
108838807
681231074
644121957
911203033
190055176
696385690
936750672
753723350
200690758
840546153
39260738
242234801
958678150
92648...

result:

ok 486061 numbers

Test #11:

score: 0
Accepted
time: 153ms
memory: 59216kb

input:

467812 448354

output:

900296606
802348859
920449046
342092877
15903803
315457190
610050785
677368557
827898162
850348006
918145269
100413429
286141122
723506730
444503335
498737569
412741085
55182144
622915390
145398304
361786018
453817918
325379444
279159566
612579035
555703010
284796267
31457982
547199941
167269220
917...

result:

ok 467812 numbers

Test #12:

score: 0
Accepted
time: 150ms
memory: 58368kb

input:

486767 465253

output:

896140171
794035989
38457645
667018451
121077123
988018258
454886247
148667810
782822242
208886808
641186382
664983537
135609621
929099937
781283105
673597413
898333512
533372308
349436050
608656262
229842701
591579717
102946839
732166129
415428398
269284759
811402014
588459181
448836208
30635772
14...

result:

ok 486767 numbers

Test #13:

score: 0
Accepted
time: 139ms
memory: 58404kb

input:

455721 231993

output:

861554085
724863817
681201785
82707070
329170451
815432452
480078531
960748236
199985657
265729483
43600900
600505341
942806449
749230414
634217227
690651435
92408500
559745153
336853395
259055628
322977700
244145248
806934059
60422830
229138080
978023704
52573139
622964643
298105514
878856237
79116...

result:

ok 455721 numbers

Test #14:

score: 0
Accepted
time: 137ms
memory: 57484kb

input:

456074 166647

output:

550779515
103314677
680704969
104574508
421361420
116643622
662147096
817326397
947520551
180619995
27083749
470585529
491549290
514402213
308761194
350599064
923257834
308640880
614091608
114961735
934141925
413458402
982181885
925717354
288272850
10675839
578069676
657318380
431067097
927121546
45...

result:

ok 456074 numbers

Test #15:

score: 0
Accepted
time: 144ms
memory: 57744kb

input:

455455 165608

output:

818811474
639378595
559603642
505656460
732593061
518746340
763553035
619494907
724183639
517533699
565002043
469308457
942905250
972176896
126587792
234342559
715415951
639986417
796466894
23149560
432288560
256012618
37970347
784640990
338731371
397938827
514010733
565833174
65243657
565593692
685...

result:

ok 455455 numbers