QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #590975 | #8635. 圆 | huaxiamengjin | 40 | 59ms | 359768kb | C++14 | 1.0kb | 2024-09-26 13:24:23 | 2024-09-26 13:24:24 |
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)*i)%NN;
pre=t1*t2%NN;
// cout<<t1<<" "<<t2<<" "<<ans<<"\n";
}
cout<<ans<<"\n";
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 9688kb
input:
3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 10
Accepted
time: 1ms
memory: 9708kb
input:
4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 10
Accepted
time: 0ms
memory: 9692kb
input:
6
output:
299473309
result:
ok 1 number(s): "299473309"
Test #4:
score: 10
Accepted
time: 1ms
memory: 9796kb
input:
10
output:
487238321
result:
ok 1 number(s): "487238321"
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 10728kb
input:
100
output:
891407104
result:
wrong answer 1st numbers differ - expected: '41620761', found: '891407104'
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 12144kb
input:
200
output:
602468661
result:
wrong answer 1st numbers differ - expected: '208771764', found: '602468661'
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 18364kb
input:
500
output:
864417048
result:
wrong answer 1st numbers differ - expected: '888621375', found: '864417048'
Test #8:
score: 0
Wrong Answer
time: 59ms
memory: 336088kb
input:
4798
output:
956019205
result:
wrong answer 1st numbers differ - expected: '319137015', found: '956019205'
Test #9:
score: 0
Wrong Answer
time: 43ms
memory: 359708kb
input:
4999
output:
736128434
result:
wrong answer 1st numbers differ - expected: '818467659', found: '736128434'
Test #10:
score: 0
Wrong Answer
time: 59ms
memory: 359768kb
input:
5000
output:
607054468
result:
wrong answer 1st numbers differ - expected: '142907477', found: '607054468'