QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #625749 | #8635. 圆 | jiaziqi | 100 ✓ | 74ms | 4008kb | C++14 | 1.0kb | 2024-10-09 20:49:26 | 2024-10-09 20:49:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ShuaiBi main
using namespace std;
typedef long long ll;
const int N=5003;
const ll mod=998244353;
ll Pow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll Inv(ll x){return Pow(x%mod,mod-2);}
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll n,ans,ji[N],inv[N],s[N];
void init(){
ji[0]=1;for(int i=1;i<=n;i++) ji[i]=ji[i-1]*i%mod;
inv[n]=Inv(ji[n]);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m){return ji[n]*inv[m]%mod*inv[n-m]%mod;}
int ShuaiBi(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
scanf("%lld",&n);
if(n==3) return puts("1"),0;
init();n--;
for(int x=1;x<=n;x++){
ll sum=0;
for(int len:{n-2,n-1,n})
for(int a=0;a<=x;a++){//a+2b+3c=len,a+b+c=x
int c=len-2*x+a,b=x-a-c;
if(a>=0 && b>=0 && c>=0) sum=(sum+C(x,a)*C(x-a,b)%mod*ji[x]%mod)%mod;
}
s[x]=sum*ji[n-x]%mod;
ans=(ans+(s[x]-s[x-1])*inv[n]%mod*x%mod)%mod;
}
printf("%lld\n",(ans%mod+mod+1)%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3760kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3916kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3828kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 0ms
memory: 3900kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 0ms
memory: 3964kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 1ms
memory: 3968kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 64ms
memory: 4008kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 70ms
memory: 4004kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 74ms
memory: 4004kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"