QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #619448 | #8635. 圆 | a_little_boy | 100 ✓ | 70ms | 3856kb | C++14 | 1.4kb | 2024-10-07 14:14:19 | 2024-10-07 14:14:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,dp[5005][3],summ,ans[5005],rans,jc[5005],ny[5005],rans2;
const ll MOD=998244353;
ll ksm(ll x,ll y){
ll ans=1;
while(y){if(y&1)ans=(ans*x)%MOD;x=(x*x)%MOD;y>>=1;}
return ans;
}
ll inline p(ll x,ll y){
if(y>x)return 0;
return jc[x]*ny[x-y]%MOD;
}
int main(){
//freopen("color.in","r",stdin);
//freopen("color.out","w",stdout);
cin>>n;
dp[1][0]=1;jc[0]=jc[1]=1;ny[0]=ny[1]=1;
if(1==n-2){for(int j=1;j<=n;j++)ans[j]+=(3*dp[j][0])%MOD,ans[j]%=MOD;}
for(int i=2;i<=n;i++){
jc[i]=(jc[i-1]*i)%MOD;ny[i]=ksm(jc[i],MOD-2);
for(int j=n;j>=1;j--){
dp[j][2]=dp[j][1];
dp[j][1]=dp[j][0];
dp[j][0]=(dp[j-1][0]+dp[j-1][1]+dp[j-1][2])%MOD;
}
if(i==n-2){for(int j=1;j<=n;j++)ans[j]+=(3*dp[j][0])%MOD,ans[j]%=MOD;}
if(i==n-1){for(int j=1;j<=n;j++)ans[j]+=(2*dp[j][0])%MOD,ans[j]%=MOD;}
if(i==n){for(int j=1;j<=n;j++)ans[j]+=(1*dp[j][0])%MOD,ans[j]%=MOD;}
}
for(int i=1;i<=n;i++)
ans[i]=(ans[i]*jc[i])%MOD;
for(int i=1;i<=n;i++){summ=0;//cout<<i<<" "<<ans[i]<<endl;
for(int j=1;j<i;j++)summ=(summ+ans[j]*p(n-j,i-j)%MOD)%MOD;
ans[i]=(ans[i]-summ)%MOD;
// cout<<i<<" "<<ans[i]<<endl;
rans=(rans+((i*ans[i]%MOD)*jc[n-i])%MOD)%MOD;
rans2=(rans2+ans[i]*jc[n-i]%MOD)%MOD;
}
// cout<<rans<<" "<<rans2<<endl;
cout<<((rans*ksm(rans2,MOD-2))%MOD+MOD)%MOD<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3640kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3640kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3712kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3644kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 0ms
memory: 3580kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 1ms
memory: 3648kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 1ms
memory: 3664kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 64ms
memory: 3856kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 70ms
memory: 3856kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 70ms
memory: 3788kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"