QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #619204 | #8635. 圆 | zwh2008 | 100 ✓ | 40ms | 198752kb | C++14 | 857b | 2024-10-07 13:30:08 | 2024-10-07 13:30:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool ST;
const int N=5005,mod=998244353;
int n,f[N][N],C[N][N];
ll ans,s[N];
ll qp(ll a,int b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
bool ED;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cerr<<"Memory: "<<(&ST-&ED)/1024.0/1024<<" MB\n";
cin>>n,C[0][0]=1;
for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%mod;
f[1][1]=1;
for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)f[i][j]=(1ll*f[i-1][j-1]+f[i-2][j-1]+(i>2?f[i-3][j-1]:0))%mod;
for(int i=1;i<=n;i++)s[i]=(s[i]+f[n][i]+f[n-1][i]+f[n-2][i])%mod;
for(int i=0;i<=n;i++) {
ll v=s[i]*n%mod*qp(i,mod-2)%mod;
ll p=v*qp(C[n][i],mod-2)%mod;
ans=(ans+mod+1-p)%mod;
}cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 7956kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 1ms
memory: 5780kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 1ms
memory: 5916kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 1ms
memory: 7968kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 1ms
memory: 10300kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 0ms
memory: 14208kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 0ms
memory: 24708kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 36ms
memory: 194360kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 40ms
memory: 198172kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 39ms
memory: 198752kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"