QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164902#6417. Classical Summation Problemxuzhihaodedie#TL 11ms19368kbC++141.2kb2023-09-05 14:35:312023-09-05 14:35:32

Judging History

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

  • [2023-09-05 14:35:32]
  • 评测
  • 测评结果:TL
  • 用时:11ms
  • 内存:19368kb
  • [2023-09-05 14:35:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define x first
//#define y second
#define PII pair<int,int>
const int N=1e6+10;
const int mod=998244353;
int fact[N],infact[N];
int qpow(int a,int b) {
	if(b==0) return 1;
	if(b&1) return a*qpow(a,b-1)%mod;
	else {
		int mul=qpow(a,b/2);
		return mul*mul%mod;
	}
}
void init() {
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	infact[N-1]=qpow(fact[N-1],mod-2);
	for(int i=N-2;i>=0;i--) infact[i]=infact[i+1]*(i+1)%mod;
} 
int c(int n,int m) {
	if(n<m) return 0;
	return fact[n]*infact[m]%mod*infact[n-m]%mod;
}
void solve() {
	int n,k;
	cin>>n>>k;
	int ans=0;
	for(int i=1;i<=n;i++) {
		for(int x=0;x<=k;x++) {
			if(2*x>=k) continue;
			for(int y=0;y<=k;y++) {
				if(2*y>k) continue;
				int res=k-x-y;
				ans=(ans+i*c(k,x)%mod*c(k-x,y)%mod*c(k-x-y,res)%mod*qpow(i-1,x)%mod*qpow(n-i,y)%mod)%mod;
				//cout<<i<<" "<<x<<" "<<k-x-y<<" "<<y<<" "<<ans<<endl;
			}
		}
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
}
signed main() {
	int T=1;
	//cin>>T;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	while(T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 19324kb

input:

3 2

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 11ms
memory: 19240kb

input:

5 3

output:

375

result:

ok 1 number(s): "375"

Test #3:

score: 0
Accepted
time: 5ms
memory: 19308kb

input:

2 2

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 7ms
memory: 19368kb

input:

10 9

output:

508778235

result:

ok 1 number(s): "508778235"

Test #5:

score: 0
Accepted
time: 10ms
memory: 19308kb

input:

69 3

output:

11497815

result:

ok 1 number(s): "11497815"

Test #6:

score: -100
Time Limit Exceeded

input:

994 515

output:


result: