QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#661795	#6417. Classical Summation Problem	ucup-team5271^#	AC ✓	356ms	11552kb	C++17	713b	2024-10-20 18:12:23	2024-10-20 18:12:23

Judging History

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

[2024-10-20 18:12:23]
评测

测评结果：AC
用时：356ms
内存：11552kb

查看

[2024-10-20 18:12:23]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6,p=998244353,I2=p+1>>1;
static int f[N+1];
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)(r*=a)%=p;
    (a*=a)%=p,b>>=1;
  }
  return r;
}
inline int com(int n,int m){
  return f[n]*qpow(f[m]*f[n-m]%p,p-2)%p;
}
main(){
  ios::sync_with_stdio(false);
  for(int i=f[0]=1;i<=N;i++)
    f[i]=f[i-1]*i%p;
  int n,k,c=0; cin>>n>>k;
  if(k&1)cout<<(n+1)*I2%p*qpow(n,k)%p<<endl,exit(0);
  for(int i=1;i<n;i++)
    chadd(c,qpow(i*(n-i)%p,k>>1)*com(k,k>>1)%p*qpow(qpow(n,k),p-2)%p);
  cout<<(n+1-c+p)*I2%p*qpow(n,k)%p<<endl;
  return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 11484kb

input:

3 2

output:

result:

ok 1 number(s): "14"

Test #2:

score: 0

Accepted

time: 6ms

memory: 11452kb

input:

5 3

output:

result:

ok 1 number(s): "375"

Test #3:

score: 0

Accepted

time: 5ms

memory: 11540kb

input:

2 2

output:

result:

ok 1 number(s): "5"

Test #4:

score: 0

Accepted

time: 3ms

memory: 11424kb

input:

10 9

output:

508778235

result:

ok 1 number(s): "508778235"

Test #5:

score: 0

Accepted

time: 6ms

memory: 11416kb

input:

69 3

output:

11497815

result:

ok 1 number(s): "11497815"

Test #6:

score: 0

Accepted

time: 0ms

memory: 11464kb

input:

994 515

output:

33689623

result:

ok 1 number(s): "33689623"

Test #7:

score: 0

Accepted

time: 3ms

memory: 11492kb

input:

4476 6182

output:

114894183

result:

ok 1 number(s): "114894183"

Test #8:

score: 0

Accepted

time: 3ms

memory: 11424kb

input:

58957 12755

output:

932388891

result:

ok 1 number(s): "932388891"

Test #9:

score: 0

Accepted

time: 70ms

memory: 11416kb

input:

218138 28238

output:

392861201

result:

ok 1 number(s): "392861201"

Test #10:

score: 0

Accepted

time: 222ms

memory: 11472kb

input:

644125 316810

output:

420621854

result:

ok 1 number(s): "420621854"

Test #11:

score: 0

Accepted

time: 216ms

memory: 11420kb

input:

612914 505428

output:

973686286

result:

ok 1 number(s): "973686286"

Test #12:

score: 0

Accepted

time: 6ms

memory: 11536kb

input:

998216 938963

output:

251335926

result:

ok 1 number(s): "251335926"

Test #13:

score: 0

Accepted

time: 5ms

memory: 11424kb

input:

990516 996933

output:

549551960

result:

ok 1 number(s): "549551960"

Test #14:

score: 0

Accepted

time: 355ms

memory: 11540kb

input:

999019 999012

output:

637189128

result:

ok 1 number(s): "637189128"

Test #15:

score: 0

Accepted

time: 354ms

memory: 11424kb

input:

999928 999950

output:

185229465

result:

ok 1 number(s): "185229465"

Test #16:

score: 0

Accepted

time: 6ms

memory: 11416kb

input:

999999 999999

output:

384164916

result:

ok 1 number(s): "384164916"

Test #17:

score: 0

Accepted

time: 346ms

memory: 11476kb

input:

999999 1000000

output:

696165930

result:

ok 1 number(s): "696165930"

Test #18:

score: 0

Accepted

time: 6ms

memory: 11536kb

input:

1000000 999999

output:

219071706

result:

ok 1 number(s): "219071706"

Test #19:

score: 0

Accepted

time: 349ms

memory: 11472kb

input:

1000000 1000000

output:

128206597

result:

ok 1 number(s): "128206597"

Test #20:

score: 0

Accepted

time: 6ms

memory: 11468kb

input:

2 10

output:

result:

ok 1 number(s): "1410"

Test #21:

score: 0

Accepted

time: 6ms

memory: 11420kb

input:

84 16

output:

297627153

result:

ok 1 number(s): "297627153"

Test #22:

score: 0

Accepted

time: 3ms

memory: 11492kb

input:

643 800

output:

489237163

result:

ok 1 number(s): "489237163"

Test #23:

score: 0

Accepted

time: 8ms

memory: 11484kb

input:

9903 880

output:

595167333

result:

ok 1 number(s): "595167333"

Test #24:

score: 0

Accepted

time: 37ms

memory: 11500kb

input:

97446 89750

output:

410205549

result:

ok 1 number(s): "410205549"

Test #25:

score: 0

Accepted

time: 70ms

memory: 11552kb

input:

186460 646474

output:

32638530

result:

ok 1 number(s): "32638530"

Test #26:

score: 0

Accepted

time: 173ms

memory: 11536kb

input:

508940 244684

output:

598321755

result:

ok 1 number(s): "598321755"

Test #27:

score: 0

Accepted

time: 204ms

memory: 11420kb

input:

583646 557758

output:

858695621

result:

ok 1 number(s): "858695621"

Test #28:

score: 0

Accepted

time: 337ms

memory: 11536kb

input:

969610 992608

output:

256683498

result:

ok 1 number(s): "256683498"

Test #29:

score: 0

Accepted

time: 343ms

memory: 11468kb

input:

995106 996434

output:

411791999

result:

ok 1 number(s): "411791999"

Test #30:

score: 0

Accepted

time: 351ms

memory: 11496kb

input:

999961 999872

output:

61222370

result:

ok 1 number(s): "61222370"

Test #31:

score: 0

Accepted

time: 355ms

memory: 11416kb

input:

999977 999908

output:

831096762

result:

ok 1 number(s): "831096762"

Test #32:

score: 0

Accepted

time: 356ms

memory: 11484kb

input:

999992 999998

output:

562977678

result:

ok 1 number(s): "562977678"

Test #33:

score: 0

Accepted

time: 222ms

memory: 11492kb

input:

1000000 2

output:

118436113

result:

ok 1 number(s): "118436113"

Test #34:

score: 0

Accepted

time: 6ms

memory: 11496kb

input:

2 1000000

output:

298823641

result:

ok 1 number(s): "298823641"