QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #472824 | #6410. Classical DP Problem | UESTC_DECAYALI | WA | 1ms | 5900kb | C++17 | 856b | 2024-07-11 19:38:53 | 2024-07-11 19:38:53 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,mod=998244353;
int n,k=1,a[N],b[N],f[N][N];
inline int solve(CI k,CI m)
{
RI i,j; for (i=0;i<=k;++i) for (j=0;j<=m;++j) f[i][j]=0;
for (f[0][0]=1,i=0;i<k;++i) for (j=0;j<=m;++j) if (f[i][j])
{
(f[i+1][j+1]+=1LL*f[i][j]*(m-j)%mod)%=mod;
(f[i+1][j]+=1LL*f[i][j]*(a[i+1]-(m-j))%mod)%=mod;
}
return f[k][m];
}
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
reverse(a+1,a+n+1); while (a[k]>k) ++k;
int ans=solve(k,a[k+1]);
for (i=1;i<=n;++i) ++b[a[i]];
for (i=n-1;i>=1;--i) b[i]+=b[i+1];
for (i=1;i<=n;++i) a[i]=b[i];
ans=(ans+solve(k,a[k+1]))%mod;
int fact=1; for (i=1;i<=k;++i) fact=1LL*fact*i%mod;
return printf("%d %d",k,(ans-fact+mod)%mod),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3812kb
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: 3896kb
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: 1ms
memory: 5900kb
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:
18 383552179
result:
wrong answer 1st numbers differ - expected: '17', found: '18'