QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472565#6417. Classical Summation ProblemUESTC_DebugSimulator#WA 14ms19352kbC++171.0kb2024-07-11 17:11:452024-07-11 17:11:46

Judging History

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

  • [2024-07-11 17:11:46]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:19352kb
  • [2024-07-11 17:11:45]
  • 提交

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'