Wavel Sequence
Problem Description
Have you ever seen the wave? It’s a wonderful view of nature. Little Q is attracted to such wonderful thing, he even likes everything that looks like wave. Formally, he defines a sequence a1,a2,…,an as ”wavel” if and only if a1a3a5
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int max_n=2009;
const int mod=998244353;
int a[max_n],b[max_n];
int n,m,num0,num1,ans;
int once[max_n][2],sum[max_n][2];///once是指以b数组中此次状态下的的第i为作为谷态(0)和峰态(1)的个数
///sum是指以b数组中之前所有的的第j位作为谷态(0)和峰态(1)的个数
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
num0=1;///表示此次作为波谷的个数，因为最开始的那个肯定要从波谷开始
num1=0;///表示此次作为波峰的个数
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])///两个相同的话，则进行状态的转移
{
once[j][0]=num0;
once[j][1]=num1;
ans=(ans+(once[j][0]+once[j][1])%mod)%mod;
}
if(a[i]>b[j])///这里作为波峰
{
num1=(num1+sum[j][0])%mod;///这次的可以作为波峰的加上之前的波谷
}
if(a[i]<b[j])
{
num0=(num0+sum[j][1])%mod;///这次的可以作为波谷的加上之前的波峰
}
}
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])
{
sum[j][0]=(sum[j][0]+once[j][0])%mod;
sum[j][1]=(sum[j][1]+once[j][1])%mod;
}
}
}
printf("%d\n",ans);
}
return 0;
}