QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133498#4937. Permutation TransformationPhantomThreshold#AC ✓18ms3904kbC++201.6kb2023-08-02 10:12:482023-08-02 10:12:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 10:12:50]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:3904kb
  • [2023-08-02 10:12:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int main()
{
	int n;
	cin>>n;
	vector<int> a(n+5);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	auto poww=[&](long long x,long long y,long long z)
	{
		long long ret=1;
		while(y)
		{
			if(y&1)ret*=x,ret%=z;
			x*=x,x%=z;
			y>>=1;
		}
		return ret;
	};
	vector<int> vis(n+5);
	int maxp2=0;
	map<int,int> mp;
	for(int i=1;i<=n;i++)
	{
		if(not vis[i])
		{
			int cnt=0;
			for(int j=i;not vis[j];j=a[j])
			{
//				cerr<<"? "<<j<<endl;
				vis[j]=1;
				cnt++;
			}
			int cp2=0;
			while(cnt%2==0)
				cnt/=2,cp2++;
			maxp2=max(maxp2,cp2);
			
//			cerr<<"cycle "<<cnt<<endl;
			
			int t=cnt;
			long long phi=1;
			for(int i=2;i*i<=t;i++)
			{
				if(t%i==0)
				{
					phi*=i-1;
					while(t%i==0)t/=i,phi*=i;
					phi/=i;
				}
			}
			if(t!=1)phi*=t-1;
			
//			cerr<<"phi "<<phi<<endl;
			
			t=phi;
			vector<int> pr;
			for(int i=2;i*i<=phi;i++)
			{
				if(phi%i==0)
				{
					pr.push_back(i);
					while(phi%i==0)phi/=i;
				}
			}
			if(phi!=1)pr.push_back(phi);
			
			phi=t;
			for(auto p:pr)
			{
//				cerr<<"trail div "<<p<<endl;
//				cerr<<t/p<<' '<<poww(2,t/p,cnt)<<endl;
				while(t%p==0 and poww(2,t/p,cnt)==1)
				{
					t/=p;
				}
			}
			
			cnt=t;
			for(int x=2;x*x<=cnt;x++)
			{
				if(cnt%x==0)
				{
					int cpk=0;
					while(cnt%x==0)
						cnt/=x,cpk++;
					mp[x]=max(mp[x],cpk);
				}
			}
			if(cnt!=1)mp[cnt]=max(mp[cnt],1);
		}
	}
	long long mul=1;
	for(auto [x,y]:mp)
	{
		for(int i=1;i<=y;i++)
			mul=(mul*x)%MOD;
	}
	cout<<(mul+maxp2)%MOD;
	return 0;
}

详细

Test #1:

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

input:

5
3 5 1 2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

8
7 5 1 6 8 2 3 4

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

1
1

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 18ms
memory: 3904kb

input:

100000
20864 34918 58550 1465 75674 30743 27235 88900 47488 50029 46054 84871 20330 72228 16506 44561 92519 97750 82891 60324 90508 39290 24663 38077 90189 30671 95476 64027 70888 90749 22566 8525 33675 16635 23392 97636 35788 89625 41966 78051 94034 15407 26545 83799 2233 10873 56946 71566 19045 44...

output:

216333199

result:

ok single line: '216333199'

Test #5:

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

input:

14040
5654 6009 6131 4703 11773 11998 4998 12737 10500 11016 6763 10135 13053 1667 12945 10168 12062 12329 9809 1172 13554 4227 5857 8597 5199 13041 1845 1612 2889 1556 4338 11927 7659 8409 1233 13034 1978 6832 13622 12056 3849 1006 3670 13140 6226 13735 3047 3349 3922 9715 3697 11902 5694 10537 357...

output:

49222142

result:

ok single line: '49222142'

Test #6:

score: 0
Accepted
time: 15ms
memory: 3872kb

input:

100000
26099 31546 24098 31277 80935 49363 8360 60556 17826 1248 723 59192 78846 17804 39019 68536 43655 6565 55374 72670 15887 27291 34447 3203 35267 62706 97777 38681 7861 9528 46702 19753 37932 83370 55972 33504 97146 21259 18464 66690 85076 23713 83611 57447 37649 42026 44322 73961 50022 72220 3...

output:

193641155

result:

ok single line: '193641155'

Test #7:

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

input:

31435
22209 2142 11768 29844 8545 24738 2619 18535 24922 6386 7527 2506 630 1332 27397 18293 7948 18880 17974 5081 31145 17802 2634 31359 25821 18891 14894 18756 29308 4403 5368 7876 19271 14440 4591 19794 7931 23123 9800 9418 29051 26687 12835 9250 23005 29500 6180 10587 27462 27646 8990 31408 1409...

output:

732408604

result:

ok single line: '732408604'

Test #8:

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

input:

99689
17265 43683 18781 15722 67972 54239 65523 45492 6069 10974 6282 33174 91425 78177 49983 34931 3137 5137 82497 68384 55054 28525 87547 8640 70501 8522 33057 46174 35961 72683 77156 58482 9611 82999 38453 50138 65303 53850 73822 86042 21746 39860 61478 35556 76604 46726 58346 20885 96302 54107 9...

output:

828117739

result:

ok single line: '828117739'

Test #9:

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

input:

99609
33799 18610 44239 81090 94041 23130 33572 64962 55295 20745 21231 14127 21885 97160 11886 58104 20260 95151 501 50047 24583 94911 10433 94341 85808 76442 31538 40510 82052 43174 8099 88774 65942 45695 41626 62308 96656 45634 97931 40542 79057 86245 65713 12385 68627 49498 23947 97022 13502 686...

output:

635651592

result:

ok single line: '635651592'

Test #10:

score: 0
Accepted
time: 8ms
memory: 3888kb

input:

99987
28697 1007 98100 17521 63883 10452 74178 19122 24297 98843 66298 52309 42455 74552 6609 63814 49255 96378 24784 37034 59634 88806 60730 7712 22861 49818 4160 15632 46742 97911 58263 42301 71001 13700 9366 45537 25798 87023 12755 19108 70856 63518 74697 14526 61276 81564 68429 80131 90752 27054...

output:

362463571

result:

ok single line: '362463571'

Test #11:

score: 0
Accepted
time: 18ms
memory: 3816kb

input:

99209
46892 26934 60828 51825 29444 25208 95481 32546 170 30616 97233 28218 95734 42948 53268 45454 25632 14317 70877 11783 10910 52624 74657 80727 21796 6535 59368 41971 15837 55534 7013 15889 65564 29574 91210 46873 15452 14339 76250 15286 77339 83651 19902 64329 64531 52957 72680 77282 58766 7308...

output:

625324893

result:

ok single line: '625324893'

Test #12:

score: 0
Accepted
time: 15ms
memory: 3904kb

input:

100000
29284 2339 82338 43206 59367 60583 95838 94024 45386 46045 43759 18631 45443 91571 17067 81596 48030 11643 39760 18031 15584 52958 68063 12026 4678 66552 48753 55108 1417 6754 95963 69557 77644 38542 44535 87100 94344 82728 33713 54277 45196 57718 44706 25406 45407 48019 16065 39470 92666 265...

output:

28543680

result:

ok single line: '28543680'

Test #13:

score: 0
Accepted
time: 13ms
memory: 3896kb

input:

100000
88225 5247 67459 81710 61997 29463 48069 91923 39229 98100 95937 90709 97503 87092 25599 14919 57449 32290 63342 43695 84452 35821 35888 4324 79417 47292 94405 73478 83151 41815 66151 74367 16120 48274 57393 1679 40636 23686 55770 71165 18103 16228 45511 4046 37430 10916 4623 80869 59531 6168...

output:

17

result:

ok single line: '17'

Test #14:

score: 0
Accepted
time: 13ms
memory: 3900kb

input:

100000
75401 58785 15719 14366 67374 28744 36467 67678 12977 77298 83200 76061 90134 90944 12209 74785 57692 13792 84661 67132 60981 25601 89113 4861 22737 11105 84897 75850 88555 22337 64304 1273 71835 92142 67475 18691 52146 91557 77023 82791 12001 94183 46198 24727 25434 5074 53699 59858 20953 62...

output:

2505

result:

ok single line: '2505'

Test #15:

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

input:

97904
79513 77332 55613 43402 82511 6039 42716 97385 89607 46921 27637 31316 68033 89344 9310 36986 29362 29161 20435 49591 34122 15913 95288 43865 4238 35268 80666 753 60400 16399 82126 62305 40423 71957 12517 39566 73124 73683 76222 70760 42568 88957 2820 50786 97529 33855 85077 80667 26028 42021 ...

output:

614216177

result:

ok single line: '614216177'

Test #16:

score: 0
Accepted
time: 18ms
memory: 3860kb

input:

100000
81010 37456 73399 24776 46259 22476 35753 69146 91121 53627 37244 35479 75563 56815 7829 41061 21551 130 17849 34157 76398 29650 8321 41583 16344 85082 84457 20132 45642 77401 36721 86406 49241 72998 23327 22681 5060 30214 2611 4526 5786 86126 59652 3557 92702 80444 88231 9875 8314 76961 3112...

output:

79955820

result:

ok single line: '79955820'

Test #17:

score: 0
Accepted
time: 13ms
memory: 3856kb

input:

100000
5077 39160 23297 62541 65167 84904 44214 25230 20151 84275 51056 28624 84842 86046 38869 92822 19082 68925 27647 16506 45354 72388 59534 20665 14843 77025 83935 39208 67406 34786 68132 60988 93840 92317 66106 71386 52320 95165 98900 94164 48170 92258 34622 38878 60145 95777 77902 70478 90694 ...

output:

17

result:

ok single line: '17'

Test #18:

score: 0
Accepted
time: 18ms
memory: 3880kb

input:

99518
20214 87406 6884 68885 80126 62429 22368 92800 44129 8983 12565 26395 75628 59602 53852 7619 75109 56178 46898 92345 55898 64656 83678 74695 4493 51080 76007 72906 531 69155 96318 19698 9382 73872 73816 38722 30601 88811 76003 28792 31078 99425 84652 4293 70905 6381 56771 44274 21650 3510 1866...

output:

12102443

result:

ok single line: '12102443'

Test #19:

score: 0
Accepted
time: 18ms
memory: 3896kb

input:

100000
24986 88867 9053 39491 97604 58077 81430 64981 18898 79287 11882 87243 52236 22300 46422 1013 82689 65472 31884 55346 36783 1629 55291 58299 19390 34755 87162 20053 20570 42087 42774 95766 34374 1006 58431 56714 71232 5250 39211 57671 13688 99697 34251 61213 65830 70697 48395 234 86905 80700 ...

output:

28879620

result:

ok single line: '28879620'

Test #20:

score: 0
Accepted
time: 18ms
memory: 3872kb

input:

100000
47301 82692 64011 38097 17423 78352 56516 76930 43951 53121 12496 69439 78946 45411 37350 8273 74430 96213 57477 74293 70512 24033 4058 24793 58047 99062 37493 45322 55349 9313 72709 61840 34384 75541 41592 68180 13044 26220 84821 56006 41719 29274 25503 60039 89022 1708 78785 17810 42557 940...

output:

17

result:

ok single line: '17'

Test #21:

score: 0
Accepted
time: 18ms
memory: 3896kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

1

result:

ok single line: '1'

Test #22:

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

input:

55686
47236 52592 1376 20801 54881 25436 37016 2063 52102 43035 29821 20748 7735 14 21516 16 15220 10035 1077 28576 1880 23260 14894 27658 28070 9789 23304 33755 12011 55025 29885 53645 54018 34 24994 40610 29559 53030 4725 39650 31489 54441 51692 13351 46432 2747 29541 52315 40202 34575 52199 52382...

output:

4

result:

ok single line: '4'

Test #23:

score: 0
Accepted
time: 17ms
memory: 3904kb

input:

90233
39922 27951 68958 30547 65280 63765 29375 57059 88635 27271 30032 78090 68028 77006 16076 32 9553 45397 41522 69954 38360 14802 54300 57984 87400 14549 73993 49201 16975 30713 41947 88222 74587 74213 20794 78970 78502 38 23743 60860 70701 68016 58486 52510 84647 69700 60783 17558 75837 31633 4...

output:

15

result:

ok single line: '15'

Test #24:

score: 0
Accepted
time: 14ms
memory: 3860kb

input:

96293
46825 8694 31998 72926 19487 29232 72753 72139 2324 16620 7639 40482 43489 33854 3939 21710 36481 70555 2724 70857 21302 57753 34617 18945 14347 87982 93111 31322 19030 15928 66710 30957 64959 21396 32855 67030 94186 40693 5790 34991 1678 49209 72870 56387 13555 26894 26720 37125 12261 32847 3...

output:

64

result:

ok single line: '64'

Test #25:

score: 0
Accepted
time: 16ms
memory: 3852kb

input:

99989
86529 93586 17218 30791 93899 23465 14702 44715 56979 4594 7135 71067 38898 80146 16181 7148 61656 17934 30023 81072 9110 68667 4398 29143 48026 58714 87708 65377 81080 89470 51335 74015 53355 14464 56136 40125 38263 29390 76693 72726 90603 34869 87640 33500 79641 15446 80418 47495 54592 38138...

output:

99988

result:

ok single line: '99988'

Test #26:

score: 0
Accepted
time: 16ms
memory: 3888kb

input:

82917
21148 78084 32740 15985 34338 23779 54181 29754 38363 63612 65396 75569 35058 1048 67814 22064 63185 74565 62382 1590 34458 10739 50221 12472 77300 9327 37310 33237 2171 38822 41525 29191 6650 65187 80175 47108 4273 59199 21818 33960 36210 579 24690 43698 56373 79682 29753 14017 43911 70446 44...

output:

27725

result:

ok single line: '27725'

Test #27:

score: 0
Accepted
time: 10ms
memory: 3688kb

input:

77106
62555 41656 3761 22293 32171 5924 14746 41 33910 46151 59825 23524 34109 55358 24833 22346 69185 27867 14447 36149 46931 45959 15057 1483 76164 64218 39558 50026 27717 26042 74844 75651 24356 10374 64759 2998 40655 7390 56937 17180 40207 3149 62208 46306 9252 60648 41507 32039 7785 53663 63016...

output:

240360126

result:

ok single line: '240360126'

Test #28:

score: 0
Accepted
time: 10ms
memory: 3624kb

input:

53870
8264 22771 47195 16972 14803 28085 44779 10240 37191 47393 41885 15937 9901 29532 39608 3316 31598 31224 49470 26313 35916 49988 14008 14861 5796 12074 1529 5126 15779 33121 38661 9446 43160 7201 53354 38367 45051 44970 36725 30234 22479 30260 38763 3187 2344 3400 22477 22485 16177 47337 16591...

output:

776144381

result:

ok single line: '776144381'

Test #29:

score: 0
Accepted
time: 10ms
memory: 3904kb

input:

97644
87219 63094 38436 43894 92574 3568 26547 56860 50255 78925 53451 61112 18118 28270 10017 22136 37460 83551 85796 88783 54642 94825 91728 4615 42166 90040 20676 38585 18223 34575 56166 3278 87997 10620 53208 48391 28127 17923 84847 55169 7633 97221 91308 38604 39387 93278 33226 49555 28301 4530...

output:

981619451

result:

ok single line: '981619451'

Test #30:

score: 0
Accepted
time: 9ms
memory: 3612kb

input:

59229
26212 3755 24831 23312 59114 5788 32461 53221 25869 27267 28900 10725 49579 28834 44258 25184 51947 20617 13460 24619 57552 30056 38818 51493 56738 34278 53839 704 58076 40202 44195 39036 11110 34616 50825 21491 2618 18658 28197 38389 23925 10463 54851 4036 19814 42559 27209 24924 12248 49976 ...

output:

141237464

result:

ok single line: '141237464'

Test #31:

score: 0
Accepted
time: 10ms
memory: 3580kb

input:

54097
296 37672 11090 7395 9838 18194 41031 21237 15123 19466 51781 16926 22478 25676 40815 18355 7595 12665 50091 48205 30508 4651 3280 32637 16608 51242 50189 41469 9749 3773 6474 32002 33997 31299 24099 2787 28071 29599 11153 1374 24014 42147 23971 16131 34285 51586 42727 7945 37693 32440 7407 26...

output:

563914999

result:

ok single line: '563914999'

Test #32:

score: 0
Accepted
time: 17ms
memory: 3868kb

input:

92086
20832 31330 9327 64555 4501 73723 84188 88712 75977 76631 61727 74423 38141 57530 15841 18256 71018 61463 81524 63267 70498 20276 56890 76320 411 50021 74260 39822 2896 82408 53626 79144 17442 90784 60260 3472 25522 85114 16124 74561 61682 46628 75067 3728 88042 86329 20176 57885 64176 37729 6...

output:

765821006

result:

ok single line: '765821006'

Test #33:

score: 0
Accepted
time: 10ms
memory: 3600kb

input:

50021
11289 36414 4830 43248 13657 42351 3116 30151 16105 25878 21371 20579 46017 35703 4116 41866 17943 20920 13865 37790 47792 26620 5035 20953 13934 29549 33276 16963 28984 37712 10982 45024 3627 12595 41702 35330 18763 3898 46925 8839 14651 32555 38014 4783 38692 25514 38076 13907 19460 35800 10...

output:

862784840

result:

ok single line: '862784840'

Test #34:

score: 0
Accepted
time: 8ms
memory: 3628kb

input:

61998
4451 45997 40112 56394 4207 4087 36106 45862 14610 40852 51499 13290 18169 50826 13232 24573 33936 39910 43559 13308 35996 15483 34506 32654 46072 53187 52292 10695 53756 24125 44950 6171 11484 18446 48307 14548 30897 43171 59929 54621 44497 5248 4622 26793 44795 50921 8203 54245 19905 43563 1...

output:

293682370

result:

ok single line: '293682370'

Test #35:

score: 0
Accepted
time: 10ms
memory: 3628kb

input:

53300
25904 4510 17861 10957 24120 4304 36894 16831 22874 23907 39384 36211 9961 22208 46281 35057 20304 3750 21223 21051 38025 17662 19820 9319 22911 26264 31547 12485 41659 8257 44579 3843 24505 45829 51439 14567 29090 38181 35223 32127 1580 38163 46785 7277 5252 23137 14531 39737 35742 44825 1222...

output:

844971053

result:

ok single line: '844971053'

Test #36:

score: 0
Accepted
time: 15ms
memory: 3864kb

input:

100000
21514 62504 67299 42423 74922 50491 87092 8930 83346 34270 43042 69855 61673 32419 32410 1641 59467 37934 63353 40324 29120 24168 89565 12035 85714 99115 93225 51669 8044 20617 97401 65033 33288 76974 45067 70955 74181 82869 7735 53865 95422 33888 17496 74814 34343 1030 24000 13571 14320 5664...

output:

745670720

result:

ok single line: '745670720'

Test #37:

score: 0
Accepted
time: 10ms
memory: 3640kb

input:

67366
29928 44901 13808 64525 55372 49101 29036 19293 4733 40677 25123 11181 22671 48953 47644 46308 12187 44932 37430 61219 25745 8913 34817 11562 40963 60887 1421 30349 57122 63067 44626 46518 63422 37031 13538 13680 16634 6872 15250 292 36597 35855 60296 62960 19392 33239 57875 34966 18338 41348 ...

output:

179454952

result:

ok single line: '179454952'

Test #38:

score: 0
Accepted
time: 17ms
memory: 3856kb

input:

85823
18077 30093 67208 18934 72111 3361 4587 12389 71818 44171 47639 49939 37488 33499 75296 6962 32724 23857 39323 44053 17416 27903 60357 61309 26384 54862 29007 7269 82620 10824 54865 805 46195 52481 80346 12085 58919 64773 67019 63634 44680 43936 74767 32626 72184 47027 71834 12713 28935 26038 ...

output:

165962

result:

ok single line: '165962'

Test #39:

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

input:

89888
61943 10135 20122 54423 15444 84456 12922 67268 75963 25723 57566 83082 3470 9439 88815 68090 34576 84341 70357 75644 37682 81685 38506 17244 15019 32227 51106 59683 31252 14978 41795 40895 84226 22494 42617 5366 29180 74676 80523 72300 70127 81482 8029 15604 72238 86829 40397 25040 5479 35907...

output:

6577131

result:

ok single line: '6577131'

Test #40:

score: 0
Accepted
time: 18ms
memory: 3900kb

input:

100000
76093 50628 91001 56780 84017 44049 42311 5699 28228 97550 60250 66781 26470 11073 85780 23334 10763 15210 49767 46583 32398 6962 5052 29681 6745 29732 5887 2742 24451 41358 8929 71110 88627 90682 29949 17673 12666 41133 44555 6183 57747 18693 12495 4422 38423 55122 58703 135 99719 61743 7970...

output:

902174691

result:

ok single line: '902174691'

Test #41:

score: 0
Accepted
time: 14ms
memory: 3580kb

input:

74498
44159 43903 49796 60267 25129 17792 35915 40164 28257 24640 46195 58670 42230 55748 28602 49739 34285 7619 1842 23880 14420 69528 38399 57175 40578 52740 20687 22902 10167 51185 20413 20439 38008 20952 19472 47219 66144 867 14289 33233 23262 39912 62294 13939 4583 38217 56318 41509 52056 49716...

output:

246060363

result:

ok single line: '246060363'

Test #42:

score: 0
Accepted
time: 18ms
memory: 3880kb

input:

100000
12135 17840 7438 63017 5333 8659 62546 7666 72702 99066 42958 82300 17406 28007 68616 16081 15154 90721 62670 43691 86989 36109 3038 3769 60727 9797 4855 93196 25141 67303 12438 69432 15033 28478 8383 4297 35475 67223 94653 20657 48768 58940 61039 1467 52414 27939 72013 60272 77269 73130 6007...

output:

852529553

result:

ok single line: '852529553'

Test #43:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

5688
5392 343 3669 3805 2102 2062 3328 431 311 3278 348 1190 2874 5028 4121 745 1740 3482 735 4201 5065 2789 1085 1043 1905 1488 5355 2978 4073 2348 1761 4236 5470 1440 2189 4845 908 1654 3810 2726 5595 4523 415 2317 117 3984 1241 2293 1971 2373 2931 1960 2648 2361 5576 1727 5230 3405 3486 3127 3979...

output:

221164

result:

ok single line: '221164'