QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #472369 | #6417. Classical Summation Problem | UESTC_xxx# | AC ✓ | 239ms | 11772kb | C++14 | 863b | 2024-07-11 15:55:56 | 2024-07-11 15:56:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e9+10,N=1e6+120,mod=1e9 + 7,cmod=998244353,INF=1e16;
LL n,m,k,root;
LL c[N];
LL qk(LL x,LL k)
{
LL re=1;
x=x%cmod;
while(k)
{
if(k&1) re=(re*x)%cmod;
x=(x*x)%cmod;
k>>=1;
}
return re;
}
LL C(LL n,LL m)
{
return qk(c[m]*c[n-m]%cmod,cmod-2)*c[n]%cmod;
}
int main()
{
//printf("%lld",dengbi(1,3,3));
c[0]=1;
for(LL i=1;i<N;i++) c[i]=(c[i-1]*i)%cmod;
scanf("%lld%lld",&n,&k);
LL ans=qk(n,k+1)-((n-1)*qk(2,cmod-2)%cmod)*qk(n,k);
ans%=cmod;
ans+=cmod;
ans%=cmod;
if(k%2==0)
{
LL mid=0;
for(int x=1;x<n;x++)
{
mid+=(C(k,k/2)*qk(x,k/2)%cmod)*qk(n-x,k/2)%cmod;
mid%=cmod;
}
mid*=qk(2,cmod-2);
mid%=cmod;
ans-=mid;
ans%=cmod;
ans+=cmod;
ans%=cmod;
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11764kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 6ms
memory: 11712kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 5ms
memory: 11760kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 5ms
memory: 11632kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 5ms
memory: 11724kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 5ms
memory: 11756kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: 0
Accepted
time: 3ms
memory: 11720kb
input:
4476 6182
output:
114894183
result:
ok 1 number(s): "114894183"
Test #8:
score: 0
Accepted
time: 6ms
memory: 11720kb
input:
58957 12755
output:
932388891
result:
ok 1 number(s): "932388891"
Test #9:
score: 0
Accepted
time: 48ms
memory: 11636kb
input:
218138 28238
output:
392861201
result:
ok 1 number(s): "392861201"
Test #10:
score: 0
Accepted
time: 145ms
memory: 11720kb
input:
644125 316810
output:
420621854
result:
ok 1 number(s): "420621854"
Test #11:
score: 0
Accepted
time: 144ms
memory: 11696kb
input:
612914 505428
output:
973686286
result:
ok 1 number(s): "973686286"
Test #12:
score: 0
Accepted
time: 6ms
memory: 11696kb
input:
998216 938963
output:
251335926
result:
ok 1 number(s): "251335926"
Test #13:
score: 0
Accepted
time: 6ms
memory: 11772kb
input:
990516 996933
output:
549551960
result:
ok 1 number(s): "549551960"
Test #14:
score: 0
Accepted
time: 235ms
memory: 11716kb
input:
999019 999012
output:
637189128
result:
ok 1 number(s): "637189128"
Test #15:
score: 0
Accepted
time: 238ms
memory: 11720kb
input:
999928 999950
output:
185229465
result:
ok 1 number(s): "185229465"
Test #16:
score: 0
Accepted
time: 6ms
memory: 11724kb
input:
999999 999999
output:
384164916
result:
ok 1 number(s): "384164916"
Test #17:
score: 0
Accepted
time: 232ms
memory: 11708kb
input:
999999 1000000
output:
696165930
result:
ok 1 number(s): "696165930"
Test #18:
score: 0
Accepted
time: 0ms
memory: 11696kb
input:
1000000 999999
output:
219071706
result:
ok 1 number(s): "219071706"
Test #19:
score: 0
Accepted
time: 232ms
memory: 11724kb
input:
1000000 1000000
output:
128206597
result:
ok 1 number(s): "128206597"
Test #20:
score: 0
Accepted
time: 6ms
memory: 11664kb
input:
2 10
output:
1410
result:
ok 1 number(s): "1410"
Test #21:
score: 0
Accepted
time: 6ms
memory: 11580kb
input:
84 16
output:
297627153
result:
ok 1 number(s): "297627153"
Test #22:
score: 0
Accepted
time: 0ms
memory: 11580kb
input:
643 800
output:
489237163
result:
ok 1 number(s): "489237163"
Test #23:
score: 0
Accepted
time: 3ms
memory: 11768kb
input:
9903 880
output:
595167333
result:
ok 1 number(s): "595167333"
Test #24:
score: 0
Accepted
time: 26ms
memory: 11704kb
input:
97446 89750
output:
410205549
result:
ok 1 number(s): "410205549"
Test #25:
score: 0
Accepted
time: 48ms
memory: 11732kb
input:
186460 646474
output:
32638530
result:
ok 1 number(s): "32638530"
Test #26:
score: 0
Accepted
time: 117ms
memory: 11664kb
input:
508940 244684
output:
598321755
result:
ok 1 number(s): "598321755"
Test #27:
score: 0
Accepted
time: 127ms
memory: 11564kb
input:
583646 557758
output:
858695621
result:
ok 1 number(s): "858695621"
Test #28:
score: 0
Accepted
time: 219ms
memory: 11720kb
input:
969610 992608
output:
256683498
result:
ok 1 number(s): "256683498"
Test #29:
score: 0
Accepted
time: 232ms
memory: 11580kb
input:
995106 996434
output:
411791999
result:
ok 1 number(s): "411791999"
Test #30:
score: 0
Accepted
time: 225ms
memory: 11640kb
input:
999961 999872
output:
61222370
result:
ok 1 number(s): "61222370"
Test #31:
score: 0
Accepted
time: 235ms
memory: 11768kb
input:
999977 999908
output:
831096762
result:
ok 1 number(s): "831096762"
Test #32:
score: 0
Accepted
time: 239ms
memory: 11760kb
input:
999992 999998
output:
562977678
result:
ok 1 number(s): "562977678"
Test #33:
score: 0
Accepted
time: 120ms
memory: 11580kb
input:
1000000 2
output:
118436113
result:
ok 1 number(s): "118436113"
Test #34:
score: 0
Accepted
time: 3ms
memory: 11728kb
input:
2 1000000
output:
298823641
result:
ok 1 number(s): "298823641"