QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#476035#9116. DRD String玩原神的都进队了 (Junlin Ye, Ruichen Dai, Chenghan Li)#AC ✓5ms11576kbC++14582b2024-07-13 17:37:042024-07-13 17:37:04

Judging History

This is the latest submission verdict.

  • [2024-07-13 17:37:04]
  • Judged
  • Verdict: AC
  • Time: 5ms
  • Memory: 11576kb
Show
  • [2024-07-13 17:37:04]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e6+5;
const int MOD=998244353;
ll ksm(ll a,int b){ll r=1;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD,b>>=1;}return r;}
ll f[MAXN];int n,m;
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	cin>>n>>m;
	f[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=(m*f[i-1]-(i&1?0:f[i/2]))%MOD;
	}
	if(~n&1) f[n]+=f[n/2];
	f[n]=ksm(m,n)-f[n];
	cout<<(f[n]%MOD+MOD)%MOD<<'\n';
	return 0;
}
Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 2

output:

40

result:

ok "40"

Test #2:

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

input:

3017 7801

output:

515391664

result:

ok "515391664"

Test #3:

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

input:

3 1

output:

1

result:

ok "1"

Test #4:

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

input:

4 7

output:

343

result:

ok "343"

Test #5:

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

input:

5 4

output:

304

result:

ok "304"

Test #6:

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

input:

8 8

output:

2355200

result:

ok "2355200"

Test #7:

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

input:

7 6

output:

54216

result:

ok "54216"

Test #8:

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

input:

1330 3031

output:

139921223

result:

ok "139921223"

Test #9:

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

input:

4946 3837

output:

64102067

result:

ok "64102067"

Test #10:

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

input:

4236 3305

output:

78581604

result:

ok "78581604"

Test #11:

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

input:

399 3245

output:

714500544

result:

ok "714500544"

Test #12:

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

input:

4881 2346

output:

28365995

result:

ok "28365995"

Test #13:

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

input:

4647 3069

output:

798067847

result:

ok "798067847"

Test #14:

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

input:

3414 4280

output:

669878613

result:

ok "669878613"

Test #15:

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

input:

1000000 1000000

output:

469217978

result:

ok "469217978"

Test #16:

score: 0
Accepted
time: 5ms
memory: 11576kb

input:

1000000 1

output:

1

result:

ok "1"

Test #17:

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

input:

418909 302156

output:

189551565

result:

ok "189551565"

Test #18:

score: 0
Accepted
time: 5ms
memory: 11360kb

input:

984572 895728

output:

567020798

result:

ok "567020798"

Test #19:

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

input:

50545 723857

output:

651400574

result:

ok "651400574"

Test #20:

score: 0
Accepted
time: 4ms
memory: 10136kb

input:

668791 286918

output:

27505324

result:

ok "27505324"

Test #21:

score: 0
Accepted
time: 5ms
memory: 11492kb

input:

898539 238506

output:

9072376

result:

ok "9072376"

Test #22:

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

input:

711024 686568

output:

221989803

result:

ok "221989803"

Test #23:

score: 0
Accepted
time: 5ms
memory: 11292kb

input:

970385 660016

output:

104842944

result:

ok "104842944"

Test #24:

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

input:

943632 224593

output:

631779281

result:

ok "631779281"

Test #25:

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

input:

26758 836991

output:

860673946

result:

ok "860673946"

Test #26:

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

input:

838661 823355

output:

34634389

result:

ok "34634389"

Test #27:

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

input:

923587 8580

output:

549615557

result:

ok "549615557"

Test #28:

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

input:

275456 449218

output:

745638801

result:

ok "745638801"

Test #29:

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

input:

96512 594328

output:

159367796

result:

ok "159367796"

Test #30:

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

input:

995445 996221

output:

785170205

result:

ok "785170205"

Test #31:

score: 0
Accepted
time: 5ms
memory: 10120kb

input:

821123 195922

output:

950462887

result:

ok "950462887"

Test #32:

score: 0
Accepted
time: 4ms
memory: 10676kb

input:

715365 748511

output:

571984302

result:

ok "571984302"

Test #33:

score: 0
Accepted
time: 5ms
memory: 10936kb

input:

867858 338674

output:

698272834

result:

ok "698272834"

Test #34:

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

input:

406213 206504

output:

201893603

result:

ok "201893603"

Test #35:

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

input:

729455 262034

output:

521537323

result:

ok "521537323"

Test #36:

score: 0
Accepted
time: 5ms
memory: 10792kb

input:

915061 381221

output:

361349035

result:

ok "361349035"

Test #37:

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

input:

426669 32501

output:

206011209

result:

ok "206011209"

Test #38:

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

input:

256786 708325

output:

287335753

result:

ok "287335753"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-04-11 19:12:26 | OpenSource Project