QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #590984 | #8635. 圆 | huaxiamengjin | 100 ✓ | 88ms | 359888kb | C++14 | 1.1kb | 2024-09-26 13:27:36 | 2024-09-26 13:27:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NN=998244353;
int n;
int f[5050][5050];
int g[5050][5050];
int h[5050][5050];
int p[100100],ni[100100],ans;
int mi(int x,int y){
int sum=1;
for (;y;y>>=1,x=x*x%NN)
if(y&1)sum=sum*x%NN;
return sum;
}
signed main(){
cin>>n;
p[0]=1;
for (int i=1;i<=n;i++)
p[i]=p[i-1]*i%NN;
ni[n]=mi(p[n],NN-2);
for (int i=n;i;i--)
ni[i-1]=ni[i]*i%NN;
f[1][1]=1;
for (int i=2;i<=n;i++)
for (int j=1;j<=i;j++)
f[i][j]=(f[i][j]+f[i-1][j-1]+f[i-2][j-1]+f[i-3][j-1])%NN;
g[2][1]=1;
for (int i=3;i<=n;i++)
for (int j=1;j<=i;j++)
g[i][j]=(g[i][j]+g[i-1][j-1]+g[i-2][j-1]+g[i-3][j-1])%NN;
h[3][1]=1;
for (int i=4;i<=n;i++)
for (int j=1;j<=i;j++)
h[i][j]=(h[i][j]+h[i-1][j-1]+h[i-2][j-1]+h[i-3][j-1])%NN;
int pre=0;
for (int i=1;i<=n;i++){
int t1=ni[n]*p[n-i]%NN*p[i]%NN;
int t2=(f[n][i]+f[n-1][i]+f[n-2][i]+g[n][i]+g[n-1][i]+h[n][i])%NN;
ans=(ans+(t1*t2-pre)%NN*i)%NN;
pre=t1*t2%NN;
// cout<<t1<<" "<<t2<<" "<<ans<<"\n";
}
cout<<(ans+NN)%NN<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 9704kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 9764kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 1ms
memory: 9772kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 0ms
memory: 9784kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 10
Accepted
time: 1ms
memory: 8832kb
input:
100
output:
41620761
result:
ok 1 number(s): "41620761"
Test #6:
score: 10
Accepted
time: 0ms
memory: 12260kb
input:
200
output:
208771764
result:
ok 1 number(s): "208771764"
Test #7:
score: 10
Accepted
time: 3ms
memory: 18208kb
input:
500
output:
888621375
result:
ok 1 number(s): "888621375"
Test #8:
score: 10
Accepted
time: 48ms
memory: 334064kb
input:
4798
output:
319137015
result:
ok 1 number(s): "319137015"
Test #9:
score: 10
Accepted
time: 56ms
memory: 359888kb
input:
4999
output:
818467659
result:
ok 1 number(s): "818467659"
Test #10:
score: 10
Accepted
time: 88ms
memory: 359808kb
input:
5000
output:
142907477
result:
ok 1 number(s): "142907477"