QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #940598 | #6417. Classical Summation Problem | fzx | AC ✓ | 220ms | 50676kb | C++14 | 1.3kb | 2025-03-17 21:04:20 | 2025-03-17 21:04:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=998244353;
const int INF=3e6+5;
const int inv2=(Mod+1)/2;
int n,k,fav[INF],ifav[INF];
int ksm(int x,int y) {
int ba=x%Mod,ans=1;
while (y) {
if (y&1) ans=(ans*ba)%Mod;
ba=(ba*ba)%Mod;y>>=1;
}
return ans;
}
void init() {
fav[0]=1;int N=3e6;
for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod;
ifav[N]=ksm(fav[N],Mod-2);
for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod;
}
int C(int x,int y) {
if (x<y) return 0;
return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod;
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>k;init();int M=(k+1)/2;
int res=0,sum1=0,sum2=0;
for (int i=0;i<=n;i++) {
sum1+=ksm(n,k);sum1%=Mod;
// for (int p=0;p<=k;p++)
// sum1+=C(k,p)*ksm(i,p)%Mod*ksm(n-i,k-p),sum1%=Mod;
}
if (k%2==0) {
for (int i=0;i<=n;i++)
for (int p=M;p<=M;p++)
sum1-=C(k,p)*ksm(i,p)%Mod*ksm(n-i,k-p),sum1%=Mod;
}
// if (n%2==0) {
// for (int p=0;p<=k;p++)
// if (k%2==0 && p==M) ;
// else sum1+=C(k,p)*ksm(n/2,p)%Mod*ksm(n-n/2,k-p),sum1%=Mod;
// }
sum1%=Mod;sum1+=Mod;sum1%=Mod;
// for (int i=0;i<=n;i++) {
// for (int p=0;p<M;p++)
// sum2+=C(k,p)*ksm(i,p)%Mod*ksm(n-i,k-p),sum2%=Mod;
// }
res+=sum1*inv2%Mod;res%=Mod;
cout<<(res)%Mod<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 25ms
memory: 50480kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 26ms
memory: 50500kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 25ms
memory: 50416kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 26ms
memory: 50536kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 23ms
memory: 50520kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 25ms
memory: 50540kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: 0
Accepted
time: 25ms
memory: 50352kb
input:
4476 6182
output:
114894183
result:
ok 1 number(s): "114894183"
Test #8:
score: 0
Accepted
time: 26ms
memory: 50528kb
input:
58957 12755
output:
932388891
result:
ok 1 number(s): "932388891"
Test #9:
score: 0
Accepted
time: 55ms
memory: 50528kb
input:
218138 28238
output:
392861201
result:
ok 1 number(s): "392861201"
Test #10:
score: 0
Accepted
time: 133ms
memory: 50480kb
input:
644125 316810
output:
420621854
result:
ok 1 number(s): "420621854"
Test #11:
score: 0
Accepted
time: 136ms
memory: 50520kb
input:
612914 505428
output:
973686286
result:
ok 1 number(s): "973686286"
Test #12:
score: 0
Accepted
time: 86ms
memory: 50676kb
input:
998216 938963
output:
251335926
result:
ok 1 number(s): "251335926"
Test #13:
score: 0
Accepted
time: 87ms
memory: 50272kb
input:
990516 996933
output:
549551960
result:
ok 1 number(s): "549551960"
Test #14:
score: 0
Accepted
time: 215ms
memory: 50428kb
input:
999019 999012
output:
637189128
result:
ok 1 number(s): "637189128"
Test #15:
score: 0
Accepted
time: 220ms
memory: 50472kb
input:
999928 999950
output:
185229465
result:
ok 1 number(s): "185229465"
Test #16:
score: 0
Accepted
time: 89ms
memory: 50536kb
input:
999999 999999
output:
384164916
result:
ok 1 number(s): "384164916"
Test #17:
score: 0
Accepted
time: 208ms
memory: 50460kb
input:
999999 1000000
output:
696165930
result:
ok 1 number(s): "696165930"
Test #18:
score: 0
Accepted
time: 88ms
memory: 50336kb
input:
1000000 999999
output:
219071706
result:
ok 1 number(s): "219071706"
Test #19:
score: 0
Accepted
time: 210ms
memory: 50444kb
input:
1000000 1000000
output:
128206597
result:
ok 1 number(s): "128206597"
Test #20:
score: 0
Accepted
time: 23ms
memory: 50544kb
input:
2 10
output:
1410
result:
ok 1 number(s): "1410"
Test #21:
score: 0
Accepted
time: 27ms
memory: 50476kb
input:
84 16
output:
297627153
result:
ok 1 number(s): "297627153"
Test #22:
score: 0
Accepted
time: 27ms
memory: 50452kb
input:
643 800
output:
489237163
result:
ok 1 number(s): "489237163"
Test #23:
score: 0
Accepted
time: 27ms
memory: 50496kb
input:
9903 880
output:
595167333
result:
ok 1 number(s): "595167333"
Test #24:
score: 0
Accepted
time: 42ms
memory: 50512kb
input:
97446 89750
output:
410205549
result:
ok 1 number(s): "410205549"
Test #25:
score: 0
Accepted
time: 59ms
memory: 50580kb
input:
186460 646474
output:
32638530
result:
ok 1 number(s): "32638530"
Test #26:
score: 0
Accepted
time: 109ms
memory: 50376kb
input:
508940 244684
output:
598321755
result:
ok 1 number(s): "598321755"
Test #27:
score: 0
Accepted
time: 125ms
memory: 50624kb
input:
583646 557758
output:
858695621
result:
ok 1 number(s): "858695621"
Test #28:
score: 0
Accepted
time: 208ms
memory: 50468kb
input:
969610 992608
output:
256683498
result:
ok 1 number(s): "256683498"
Test #29:
score: 0
Accepted
time: 211ms
memory: 50588kb
input:
995106 996434
output:
411791999
result:
ok 1 number(s): "411791999"
Test #30:
score: 0
Accepted
time: 209ms
memory: 50536kb
input:
999961 999872
output:
61222370
result:
ok 1 number(s): "61222370"
Test #31:
score: 0
Accepted
time: 215ms
memory: 50496kb
input:
999977 999908
output:
831096762
result:
ok 1 number(s): "831096762"
Test #32:
score: 0
Accepted
time: 216ms
memory: 50560kb
input:
999992 999998
output:
562977678
result:
ok 1 number(s): "562977678"
Test #33:
score: 0
Accepted
time: 39ms
memory: 50436kb
input:
1000000 2
output:
118436113
result:
ok 1 number(s): "118436113"
Test #34:
score: 0
Accepted
time: 24ms
memory: 50432kb
input:
2 1000000
output:
298823641
result:
ok 1 number(s): "298823641"