QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #630404 | #6410. Classical DP Problem | mayunfei | WA | 1ms | 6084kb | C++17 | 950b | 2024-10-11 18:21:47 | 2024-10-11 18:21:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005,p=998244353;
int n,r,m,a[maxn],b[maxn],f[maxn][maxn],v[5],jcr=1,loc;
int main()
{
scanf("%d",&n),loc=n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(r<n&&a[n-r]>r) (jcr*=(++r))%=p;
f[n-r][0]=1;
for(int i=1;i<=a[n-r];i++) f[n-r][i]=0;
for(int i=n-r+1;i<=n;i++)
for(int j=0;j<=a[n-r];j++)
f[i][j]=(1ll*(j+a[i]-a[n-r])*f[i-1][j]+(j?(a[n-r]-j+1ll)*f[i-1][j-1]:0))%p;
v[1]=f[n][a[n-r]],m=a[n];
for(int i=m;i>=1;i--)
{
while(loc>1&&a[loc-1]>=i) loc--;
b[m-i+1]=n-loc+1;
}
// for(int i=1;i<=m;i++) cerr<<b[i]<<",";
// cerr<<endl;
f[m-r][0]=1;
for(int i=1;i<=b[m-r];i++) f[m-r][i]=0;
for(int i=m-r+1;i<=m;i++)
for(int j=0;j<=b[m-r];j++)
f[i][j]=(1ll*(j+b[i]-b[m-r])*f[i-1][j]+(j?(b[m-r]-j+1ll)*f[i-1][j-1]:0))%p;
v[2]=f[m][b[m-r]];
// cerr<<v[1]<<"+"<<v[2]<<"-"<<jcr<<endl;
printf("%d %d\n",r,((v[1]+v[2]-jcr)%p+p)%p);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3916kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
10 2 4 5 5 5 5 6 8 8 10
output:
5 864
result:
ok 2 number(s): "5 864"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 6084kb
input:
30 6 8 9 9 9 10 13 14 15 15 16 17 17 18 20 22 22 23 23 24 24 25 25 25 27 28 28 29 29 30
output:
17 843284081
result:
wrong answer 2nd numbers differ - expected: '986189864', found: '843284081'