QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#869988 | #2546. High Powers | zhicheng | AC ✓ | 1ms | 3840kb | C++14 | 1.4kb | 2025-01-25 14:17:26 | 2025-01-25 14:17:37 |
Judging History
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'