QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #155642 | #6410. Classical DP Problem | Forever_Young# | WA | 7ms | 203208kb | C++14 | 828b | 2023-09-01 22:37:05 | 2023-09-01 22:37:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,a[5050],r,dp[2][5050][5050],res,fac[5050];
const int mo=998244353;
int main(){
//freopen("D.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=n;i;i--){
if (r>=a[i]) break;
r++;
}
dp[0][n][a[n-r]]=1;
for (int i=n;i>n-r;i--)
for (int j=0;j<=a[n-r];j++){
//printf("%d %d %d\n",i,j,dp[0][i][j]);
dp[0][i-1][j]=(dp[0][i-1][j]+1ll*dp[0][i][j]*(a[i]-j))%mo;
if (j)
dp[0][i-1][j-1]=(dp[0][i-1][j-1]+1ll*dp[0][i][j]*j)%mo;
}
res=dp[0][n-r][0];
memset(dp,0,sizeof(dp));
if (r==a[n-r+1]){
fac[0]=1;
for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo;
for (int i=1;i<=n-r;i++)
res=(res+1ll*a[i]*fac[r-1])%mo;
res=(res+1ll*fac[r]*(r-1)%mo*499122177)%mo;
}
printf("%d %d\n",r,res);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 202996kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 203208kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 7ms
memory: 203100kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 203004kb
input:
2 2 2
output:
2 5
result:
wrong answer 2nd numbers differ - expected: '6', found: '5'