AcWing 682. 丢失的序列-java
原题链接
中等
作者:
单箭头
,
2019-05-11 16:44:15
,
所有人可见
,
阅读 1592
Java 代码
public class 丢失的序列 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long mod=998244353;
int N=sc.nextInt();
int[] arr=new int[N+10];
for (int i=1;i<=N;i++){
arr[i]=sc.nextInt();
}
long[][][] res=new long[N+10][210][3];
long[] s1=new long[210];
long[] s2=new long[210];
//初始化
for (int i=(arr[1]==0?1:arr[1]);i<=(arr[1]==0?200:arr[1]);i++){
for(int j=(arr[2]==0?1:arr[2]);j<=(arr[2]==0?200:arr[2]);j++){
if(i==j) res[2][j][1]++;
else if(i<j) res[2][j][2]++;
}
}
for(int j=1;j<=200;j++){
s1[j]=s1[j-1]+res[2][j][0]+res[2][j][1]+res[2][j][2];
s2[j]=s2[j-1]+res[2][j][0]+res[2][j][1];
}
//更新结构
for(int i=3;i<=N;i++){
for(int j=(arr[i]==0?1:arr[i]);j<=(arr[i]==0?200:arr[i]);j++){
res[i][j][0]=(s2[200]-s2[j])%mod;
res[i][j][1]=(res[i-1][j][0]+res[i-1][j][1]+res[i-1][j][2])%mod;
res[i][j][2]=s1[j-1]%mod;
}
for (int j=1;j<=200;j++){
s1[j]=s1[j-1]+res[i][j][0]+res[i][j][1]+res[i][j][2];
s2[j]=s2[j-1]+res[i][j][0]+res[i][j][1];
}
}
long ans=0;
for (int j=(arr[N]==0?1:arr[N]);j<=(arr[N]==0?200:arr[N]);j++){
ans=(ans+res[N][j][0]+res[N][j][1])%mod;
}
System.out.println(ans);
}
}