QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #472358 | #6417. Classical Summation Problem | UESTC_xxx# | WA | 6ms | 11760kb | C++14 | 837b | 2024-07-11 15:52:58 | 2024-07-11 15:53:01 |
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;
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(int 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*=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: 6ms
memory: 11624kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11760kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 6ms
memory: 11700kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 6ms
memory: 11656kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11580kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 5ms
memory: 11640kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: -100
Wrong Answer
time: 6ms
memory: 11584kb
input:
4476 6182
output:
70132572
result:
wrong answer 1st numbers differ - expected: '114894183', found: '70132572'