QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472565 | #6417. Classical Summation Problem | UESTC_DebugSimulator# | WA | 14ms | 19352kb | C++17 | 1.0kb | 2024-07-11 17:11:45 | 2024-07-11 17:11:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define md 998244353
#define N 1000010
int n,k;
int f[N],inv[N];
int ans,x;
int C(int m,int n)
{
if(n>m) return 0;
return(f[m]*inv[m-n]%md*inv[n]%md);
}
int qp(int a,int n)
{
int res=1;
while(n)
{
if(n&1) res=res*a%md;
a=a*a%md;
n>>=1;
}
return res;
}
int invv(int a)
{
return qp(a,md-2);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
f[0]=f[1]=inv[0]=inv[1]=1;
for(int i=2;i<=1e6;i++) f[i]=f[i-1]*i%md,inv[i]=(md-md/i)*inv[md%i]%md;
for(int i=1;i<=1e6;i++) inv[i]=inv[i-1]*inv[i]%md;
cin>>n>>k;
if(k&1)
{
ans=qp(n,k)*(n+1)*invv(2);
ans=ans%md;
cout<<ans<<"\n";
}
else
{
ans=qp(n,k)*(n+1)%md*invv(2)%md;
//cout<<ans<<"\n";
x=0;
int n1=k/2;
for(int i=1;i<=n;i++)
{
x=(x+(C(k,n1)%md*qp(i,n1)%md*qp(n-i,n1)%md))%md;
}
//cout<<x<<"\n";
//x=x*invv(qp(n,k))%md;
x=x*invv(2)%md;
ans=ans-x;
while(ans<0) ans=ans+md;
cout<<ans<<"\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 9ms
memory: 19300kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 10ms
memory: 19272kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 13ms
memory: 19300kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 9ms
memory: 19276kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 14ms
memory: 19212kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: -100
Wrong Answer
time: 9ms
memory: 19352kb
input:
994 515
output:
497036724
result:
wrong answer 1st numbers differ - expected: '33689623', found: '497036724'