QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #776768 | #8635. 圆 | bai_hong | 100 ✓ | 15ms | 56492kb | C++14 | 1.1kb | 2024-11-23 20:53:28 | 2024-11-23 20:53:30 |
Judging History
answer
//Shirosaki Hana kawaii
#include<bits/stdc++.h>
const int mod=998244353;
const int QWQ=5e3+5;
using namespace std;
using LL=long long;
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar())
if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
int n,f[QWQ][QWQ],fac[QWQ],ivn,g[QWQ],res;
inline int plu(int x){ return x>=mod ? x-mod:x; }
inline int kkk(int a,int b,int r=1){
for (;b;b>>=1,a=(LL)a*a%mod)
if (b&1) r=(LL)r*a%mod; return r;
}
signed main(){
n=read(),fac[0]=1;
if (n<4) printf("1"),exit(0);
f[1][1]=f[1][2]=f[1][3]=1,n--;
for (int i=1;i<=n;i++)
fac[i]=(LL)fac[i-1]*i%mod;
ivn=kkk(fac[n],mod-2);
for (int i=2;i<=n;i++)
for (int j=i;j<=min(3*i+1,n);j++){
f[i][j]=plu(f[i][j]+f[i-1][j-1]);
f[i][j]=plu(f[i][j]+f[i-1][j-2]);
f[i][j]=plu(f[i][j]+f[i-1][j-3]);
}
for (int i=1;i<=n;i++){
LL t=(LL)f[i][n]+f[i][n-1]+f[i][n-2];
g[i]=t*fac[i]%mod*fac[n-i]%mod;
res=plu(res+(LL)plu(g[i]-g[i-1]+mod)*i%mod);
}
printf("%d",(LL)res*ivn%mod+1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3752kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3844kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3844kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3788kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 1ms
memory: 4184kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 1ms
memory: 4676kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 2ms
memory: 6152kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 8ms
memory: 53036kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 3ms
memory: 56492kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 15ms
memory: 56396kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"