QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #591053 | #8635. 圆 | lvkaiyi0811 | 100 ✓ | 16ms | 3756kb | C++14 | 583b | 2024-09-26 13:50:24 | 2024-09-26 13:50:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll _=5005,M=998244353;
inline ll qp(ll x,ll y){ll z=1;for(;y;y>>=1,x=x*x%M)if(y&1)z=z*x%M;return z;}
ll n,x,s,a[_],b[_],c[_],i,j;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;a[0]=1;
for(j=1;j<=n;j++){
for(i=j;i;i--)c[i]=b[i],b[i]=a[i],a[i]=(a[i-1]+b[i-1]+c[i-1])%M;
c[0]=b[0],b[0]=a[0],a[0]=0;
}
for(x=i=1;i<=n;i++)(a[i]*=x)%=M,(x*=i)%=M;
for(x=i=1;i<=n;i++)(a[i]*=qp(x,M-2))%=M,(x*=n-i)%=M;
for(i=n;i;i--)(a[i]+=M-a[i-1])%=M,(s+=a[i]*i)%=M;
cout<<s<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3592kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3664kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3588kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3712kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 0ms
memory: 3584kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 0ms
memory: 3648kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 1ms
memory: 3576kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 11ms
memory: 3756kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 16ms
memory: 3748kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 16ms
memory: 3692kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"