QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #232908 | #6410. Classical DP Problem | ksun | WA | 1ms | 5900kb | C++14 | 1.4kb | 2023-10-31 00:31:31 | 2023-10-31 00:31:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,a[5001],k,x,dp1[5001][5001],dp2[5001][5001],v[5001];
long long factorial(long long n)
{
long long nr=1;
for(long long i=1;i<=n;i++)
nr=(nr*i)%mod;
return nr;
}
void rotire()
{
for(long long i=1;i<=n;i++)
{
long long j=1;
while(j<=n and a[j]>=i)
j++;
v[i]=j-1;
}
for(int i=1;i<=n;i++)
a[i]=v[i];
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++)
cin>>a[i];
reverse(a+1,a+n+1);
for(long long i=1;i<=n;i++)
{
if(a[i]>=i)
k=i;
else
break;
}
x=a[k+1];
dp1[0][x]=1;
for(long long i=0;i<=k;i++)
{
for(long long j=0;j<=x;j++)
{
if(j>0)
dp1[i+1][j-1]+=dp1[i][j]*j;
dp1[i+1][j]+=dp1[i][j]*(a[i+1]-j);
}
}
rotire();
x=a[k+1];
dp2[0][x]=1;
for(long long i=0;i<=k;i++)
{
for(long long j=0;j<=x;j++)
{
if(j>0)
dp2[i+1][j-1]+=dp2[i][j]*j;
dp2[i+1][j]+=dp2[i][j]*(a[i+1]-j);
}
}
long long total=0;
total=dp1[k][0]+dp2[k][0]-factorial(k);
total%=mod;
while(total<0)
total+=mod;
cout<<k<<" "<<total;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5448kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5436kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5444kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5416kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5464kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5432kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5468kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5588kb
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: 0
Accepted
time: 1ms
memory: 5452kb
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 986189864
result:
ok 2 number(s): "17 986189864"
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 5900kb
input:
123 1 1 1 2 2 3 3 6 6 7 7 7 8 8 9 9 10 10 10 11 12 12 12 13 14 14 14 14 16 17 17 17 17 17 18 19 20 20 21 21 22 22 22 23 23 23 25 25 26 27 27 28 28 28 28 29 29 30 31 31 31 32 33 33 33 34 35 35 35 36 37 37 38 39 39 39 39 40 41 41 42 42 42 43 44 48 48 50 52 53 55 56 57 57 57 58 65 68 71 74 75 76 76 82 ...
output:
42 859773399
result:
wrong answer 2nd numbers differ - expected: '287179924', found: '859773399'