QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #619850 | #8635. 圆 | NATO | 100 ✓ | 15ms | 198392kb | C++14 | 1.0kb | 2024-10-07 15:39:09 | 2024-10-07 15:39:10 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
ll n;
ll dp[5005][5005];
ll g[5005],f[5005];
ll mol(ll x)
{
return x>=MOD?x-MOD:x;
}
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%MOD;
a=a*a%MOD;b>>=1;
}
return res;
}
ll get_val(ll i)
{
return mol(g[i]*f[i]%MOD*f[n-i]%MOD-g[i-1]*f[i-1]%MOD*f[n-i+1]%MOD+MOD);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
if(n<=3)
{
cout<<"1";return 0;
}
--n;
dp[1][1]=dp[1][2]=dp[1][3]=dp[0][0]=1;
for(ll i=2;i<=n;++i)
for(ll j=i;j<=min(n,3*i);++j)
dp[i][j]=mol(mol(dp[i-1][j-1]+dp[i-1][j-2]+((j-3<0)?0:dp[i-1][j-3])));
f[0]=1;
for(ll i=1;i<=n;++i)
{
g[i]=mol(dp[i-1][n-3]+g[i]);
g[i]=mol(dp[i-1][n-2]+g[i]);
g[i]=mol(dp[i-1][n-1]+g[i]);
g[i]=mol(dp[i][n-2]+g[i]);
g[i]=mol(dp[i][n-1]+g[i]);
f[i]=f[i-1]*i%MOD;
}
ll res=0;
for(ll i=1;i<=n;++i)
res=mol(res+get_val(i)*i%MOD);
cout<<mol(res*qpow(f[n],MOD-2)%MOD+1);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3672kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3600kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3684kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3756kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 1ms
memory: 7920kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 0ms
memory: 12000kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 0ms
memory: 24172kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 11ms
memory: 192148kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 15ms
memory: 198364kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 12ms
memory: 198392kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"