QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#869988#2546. High PowerszhichengAC ✓1ms3840kbC++141.4kb2025-01-25 14:17:262025-01-25 14:17:37

Judging History

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

  • [2025-01-25 14:17:37]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3840kb
  • [2025-01-25 14:17:26]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
void adc(int &x,int y){
	x+=y;
	if(x>=mod){
		x-=mod;
	}
}
struct mat{
	int a[3][3];
	mat operator*(mat b){
		mat c;
		for(int i=0;i<=2;i++){
			for(int j=0;j<=2;j++){
				c.a[i][j]=0;
				for(int k=0;k<=2;k++){
					adc(c.a[i][j],1ll*a[i][k]*b.a[k][j]%mod);
				}
			}
		}
		return c;
	}
}d,s1,t1,tmp;
mat qpow(mat a,ll b){
	mat ans=a;
	b--;
	while(b){
		if(b&1){
			ans=ans*a;
		}
		a=a*a;
		b>>=1;
	}
	return ans;
}
int main(){
	int s,t,u;
	ll n,m;
	d.a[0][1]=d.a[1][2]=1;
	scanf("%lld%lld%d%d%d",&n,&m,&s,&t,&u);
	if(n<=2&&m<=2){
		if(n==1&&m==2){
			printf("1");
		}
		else if(n==2&&m==1){
			printf("%d",mod-1);
		}
		else{
			printf("0");
		}
		return 0;
	}
	if(n==0||m==0){
		printf("0");
		return 0;
	}
	d.a[0][0]=s;
	d.a[1][0]=mod-t;
	d.a[2][0]=u;
	if(m==1){
		s1.a[0][0]=mod-1;
		printf("%d",(s1*qpow(d,n-2)).a[0][0]);
		return 0;
	}
	else if(m==2){
		s1.a[0][1]=1;
		printf("%d",(s1*qpow(d,n-2)).a[0][0]);
		return 0;
	}
	tmp=qpow(d,m-2);
	s1.a[0][0]=1;
	t1.a[0][1]=(s1*tmp).a[0][0];
	s1.a[0][0]=0;
	s1.a[0][1]=mod-1;
	t1.a[0][0]=(s1*tmp).a[0][0];
	if(n==1){
		printf("%d",t1.a[0][1]);
		return 0;
	}
	else if(n==2){
		printf("%d",t1.a[0][0]);
		return 0;
	}
	printf("%d",(t1*qpow(d,n-2)).a[0][0]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

2 3
314 159 265

output:

159

result:

ok answer is '159'

Test #2:

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

input:

1000000000000000000 800000000000000000
6 11 6

output:

76083766

result:

ok answer is '76083766'

Test #3:

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

input:

1000000000000000000 500000000000000000
505459328 165146837 982639180

output:

228155372

result:

ok answer is '228155372'

Test #4:

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

input:

10 6
433449568 634776075 975070879

output:

702221465

result:

ok answer is '702221465'

Test #5:

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

input:

7 1
186852153 596868096 602573197

output:

60705736

result:

ok answer is '60705736'

Test #6:

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

input:

4 5
212703321 915061238 103724400

output:

30924996

result:

ok answer is '30924996'

Test #7:

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

input:

8 4
551085284 605657204 851045014

output:

528334108

result:

ok answer is '528334108'

Test #8:

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

input:

6 2
212931100 867878324 724964805

output:

801351015

result:

ok answer is '801351015'

Test #9:

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

input:

4 8
239538515 431946908 459468442

output:

162770307

result:

ok answer is '162770307'

Test #10:

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

input:

7 1
592269449 84082693 503088239

output:

17833887

result:

ok answer is '17833887'

Test #11:

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

input:

8 6
68796670 437893641 799659578

output:

851221125

result:

ok answer is '851221125'

Test #12:

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

input:

2 10
360999008 190606089 384676634

output:

193895611

result:

ok answer is '193895611'

Test #13:

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

input:

2 7
951765317 163234533 734030922

output:

943262686

result:

ok answer is '943262686'

Test #14:

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

input:

951 586
433449568 634776075 975070879

output:

964996550

result:

ok answer is '964996550'

Test #15:

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

input:

626 75
186852153 596868096 602573197

output:

62890492

result:

ok answer is '62890492'

Test #16:

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

input:

321 409
212703321 915061238 103724400

output:

695171764

result:

ok answer is '695171764'

Test #17:

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

input:

775 378
551085284 605657204 851045014

output:

588779865

result:

ok answer is '588779865'

Test #18:

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

input:

509 134
212931100 867878324 724964805

output:

653645300

result:

ok answer is '653645300'

Test #19:

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

input:

325 763
239538515 431946908 459468442

output:

192659414

result:

ok answer is '192659414'

Test #20:

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

input:

628 14
592269449 84082693 503088239

output:

831404486

result:

ok answer is '831404486'

Test #21:

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

input:

728 546
68796670 437893641 799659578

output:

759699603

result:

ok answer is '759699603'

Test #22:

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

input:

146 994
360999008 190606089 384676634

output:

943476896

result:

ok answer is '943476896'

Test #23:

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

input:

118 670
951765317 163234533 734030922

output:

712504442

result:

ok answer is '712504442'

Test #24:

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

input:

979 987
340955592 551141903 412969142

output:

153734653

result:

ok answer is '153734653'

Test #25:

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

input:

961 955
766525490 186347596 226693311

output:

583340770

result:

ok answer is '583340770'

Test #26:

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

input:

999 982
579693159 48311926 162088741

output:

724790834

result:

ok answer is '724790834'

Test #27:

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

input:

950 983
61813330 332962168 62071812

output:

44924776

result:

ok answer is '44924776'

Test #28:

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

input:

956 963
705190794 301186849 767800874

output:

641475961

result:

ok answer is '641475961'

Test #29:

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

input:

86112 12065
483007144 620780969 782265773

output:

705136576

result:

ok answer is '705136576'

Test #30:

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

input:

32088 65283
946471991 721151538 331133670

output:

588573766

result:

ok answer is '588573766'

Test #31:

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

input:

1281 6703
729407401 713378458 369545239

output:

642047631

result:

ok answer is '642047631'

Test #32:

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

input:

80971 53418
605017829 205998702 932389474

output:

989960794

result:

ok answer is '989960794'

Test #33:

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

input:

24138 98492
427290839 568646788 208340399

output:

393028454

result:

ok answer is '393028454'

Test #34:

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

input:

50147 97264
534975918 385213391 693633524

output:

494475535

result:

ok answer is '494475535'

Test #35:

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

input:

64418 84523
990028676 645198503 345375888

output:

773228923

result:

ok answer is '773228923'

Test #36:

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

input:

4650 18278
146242039 367055935 403091507

output:

600294257

result:

ok answer is '600294257'

Test #37:

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

input:

49634 58623
129066610 686305517 721183943

output:

589384117

result:

ok answer is '589384117'

Test #38:

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

input:

10942 56718
747670767 102414888 762025407

output:

762624131

result:

ok answer is '762624131'

Test #39:

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

input:

99918 99928
244192322 150885621 547951880

output:

890812120

result:

ok answer is '890812120'

Test #40:

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

input:

99766 99810
982311281 197766759 4149943

output:

431927523

result:

ok answer is '431927523'

Test #41:

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

input:

99843 99659
992332863 781240722 544964365

output:

269257781

result:

ok answer is '269257781'

Test #42:

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

input:

99858 99571
196177618 963862982 413729852

output:

309497560

result:

ok answer is '309497560'

Test #43:

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

input:

99878 99630
437208734 589524439 936487272

output:

357252906

result:

ok answer is '357252906'

Test #44:

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

input:

469142948102204937 778431775617655295
633960783 240965744 464058194

output:

951914410

result:

ok answer is '951914410'

Test #45:

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

input:

966325951079234617 542213011567201042
856309469 670637272 54171089

output:

333175135

result:

ok answer is '333175135'

Test #46:

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

input:

534578109193552935 385762541058301012
320932086 962261180 970667144

output:

49564830

result:

ok answer is '49564830'

Test #47:

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

input:

174089044250811872 264397017591962690
461762286 450437719 970861177

output:

100283243

result:

ok answer is '100283243'

Test #48:

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

input:

178030486578043089 735106637570292449
937064164 573784914 945031155

output:

936446795

result:

ok answer is '936446795'

Test #49:

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

input:

452888882096599848 404962052625632237
183895534 824223132 729190678

output:

504240966

result:

ok answer is '504240966'

Test #50:

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

input:

234634236986965656 213377932574259747
151649314 558843442 244903755

output:

464316803

result:

ok answer is '464316803'

Test #51:

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

input:

695197450445381038 384059490504620010
179345243 398340604 479963825

output:

159760571

result:

ok answer is '159760571'

Test #52:

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

input:

469825624683390037 51826258634376716
910595188 493389542 57801856

output:

695204971

result:

ok answer is '695204971'

Test #53:

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

input:

550084344779409062 19218550059026884
927703878 145480062 550961282

output:

958847809

result:

ok answer is '958847809'

Test #54:

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

input:

999999999999999819 999999999999999170
354240562 725536301 630405205

output:

339499639

result:

ok answer is '339499639'

Test #55:

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

input:

999999999999999128 999999999999999969
660257373 651338385 409207542

output:

851818275

result:

ok answer is '851818275'

Test #56:

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

input:

999999999999999537 999999999999999469
337330027 281844601 405661705

output:

257185591

result:

ok answer is '257185591'

Test #57:

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

input:

999999999999999438 999999999999999439
407930328 804653955 159305108

output:

609138014

result:

ok answer is '609138014'

Test #58:

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

input:

999999999999999827 999999999999999649
672662568 416952582 688394787

output:

752342119

result:

ok answer is '752342119'