QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377433#6196. Minimum Element ProblemlexiyvvAC ✓683ms166020kbC++143.5kb2024-04-05 13:31:332024-04-05 13:31:37

Judging History

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

  • [2024-04-05 13:31:37]
  • 评测
  • 测评结果:AC
  • 用时:683ms
  • 内存:166020kb
  • [2024-04-05 13:31:33]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,f[1000005],m,g[1000005],w[1000005],e[1000005],u1[1000005],u2[1000005],all[1000005];
int jc[1000005],inv[1000005];
int fm(int x,int y){
	int res=1;
	while(y){
		if(y&1)(res*=x)%=mod;
		(x*=x)%=mod,y/=2;
	}
	return res;
}
void init(){
    jc[0]=jc[1]=1;
    for(int i=2;i<=1000001;i++)
    jc[i]=(jc[i-1]%mod*i%mod)%mod;
    for(int i=0;i<=1000001;i++)inv[i]=fm(jc[i],mod-2);
}
long long C(int a,int b){
    return jc[a]%mod*inv[b]%mod*inv[a-b]%mod;
}
	const int NR = 1 << 22, gg = 3, gi = 332748118;
struct{
	typedef long long ll;
	int n, m, rev[NR+5];
	long long a[NR+5], b[NR+5];
	ll fast_power(ll a, ll k)
	{
	    ll res = 1;
	    while (k)
	    {
	        if (k & 1)
	            res = res * a % mod;
	        a = a * a % mod;
	        k >>= 1;
	    }
	    return res;
	}
	void NTT(ll *a, int n, int type)
	{
	    for (int i = 0; i < n; ++i)
	        if (i < rev[i])
	            swap(a[i], a[rev[i]]);
	    for (int i = 1; i < n; i <<= 1)
	    {                       
	        ll gn = fast_power(type ? gg : gi, (mod - 1) / (i << 1));
	        for (int j = 0; j < n; j += (i << 1)) 
	        {
	            ll g0 = 1;
	            for (int k = 0; k < i; ++k, g0 = g0 * gn % mod)
	            {
	                ll x = a[j + k], y = g0 * a[i + j + k] % mod;
	                a[j + k] = (x + y) % mod;
	                a[i + j + k] = (x - y + mod) % mod;
	            }
	        }
	    }
	}
	void calc(int *aa,int *bb,int *c,int nn,int mm){
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(rev,0,sizeof(rev));
		n=nn;m=mm;
		for(int i=0;i<=n;i++)a[i]=aa[i];
		for(int i=0;i<=m;i++)b[i]=bb[i];
	    int len = 1 << max((int)ceil(log2(n + m)), 1ll); 
	    for (int i = 0; i < len; ++i) 
	        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (max((int)ceil(log2(n + m)), 1ll) - 1));
	    NTT(a, len, 1);
	    NTT(b, len, 1);
	    for (int i = 0; i <= len; ++i)
	        a[i] = a[i] * b[i] % mod; 
	    NTT(a, len, 0); 
	    ll inv = fast_power(len, mod - 2); 
	    for (int i = 0; i <= n + m; ++i)
		c[i]=a[i]*inv%mod; 
//	        printf("%lld ", a[i] * inv % mod);
//	    return 0;
	}
}NTT;
int mul1[1000006],mul2[1000006];
signed main(){
//	 freopen("schrodingerstomb.in","r",stdin);
//	 freopen("schrodingerstomb.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
	init();
	cin>>n>>m;
	f[1]=1;f[0]=1;
	for(int i=2;i<=n;i++)
	f[i]=C(i*2,i)*fm(i+1,mod-2)%mod;
	for(int i=m;i<=m;i++)
		for(int j=0;j<i;j++)
		u1[i-j-1]=C(i+j-1,i-1)*(i-j)%mod*fm(i,mod-2)%mod*inv[i-j-1]%mod;
	for(int i=n-m+1;i<=n-m+1;i++)
		for(int j=0;j<i;j++)
		u2[i-j-1]=C(i+j-1,i-1)*(i-j)%mod*fm(i,mod-2)%mod*inv[i-j-1]%mod;
	NTT.calc(u1,u2,w,n,n);
	for(int i=0;i<=n;i++)
	(w[i]*=jc[i])%=mod;
//	for(int i=0;i<=n;i++)
//		for(int j=0;j<=n;j++)
//		(w[i+j]+=u1[i+1]*u2[j+1]%mod*jc[i+j])%=mod;
	for(int i=1;i<=n;i++)
	(w[i]+=w[i-1])%=mod;
	memset(u1,0,sizeof(u1));
	memset(u2,0,sizeof(u2));
	for(int i=0;i<m;i++)u1[i]=f[i];
	for(int j=0;j<n-m+1;j++)u2[j]=f[j];
	NTT.calc(u1,u2,all,n,n);
//	for(int i=0;i<m;i++)
//		for(int j=0;j<n-m+1;j++)
//		all[i+j+1]+=f[i]*f[j]%mod;
	for(int len=2;len<=n;len++)
	(e[len]+=f[n-len]*all[len-1])%=mod;
	for(int i=n;i>=1;i--)
	(e[i]+=e[i+1])%=mod;
	for(int t=1;t<=n;t++){
		g[t]=(w[t-1])%mod;
		int del=0;
		g[t]=(g[t]-e[n-t+2]+mod)%mod;
	}
	for(int i=1;i<=n;i++)
	cout<<g[i]<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 126ms
memory: 139272kb

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

input:

10 5

output:

588
1176
2716
4942
7407
9101
9636
9167
7596
4862

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 644ms
memory: 166020kb

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

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

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

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

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

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

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

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

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

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

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

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

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