QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164902 | #6417. Classical Summation Problem | xuzhihaodedie# | TL | 11ms | 19368kb | C++14 | 1.2kb | 2023-09-05 14:35:31 | 2023-09-05 14:35:32 |
Judging History
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