//#pragma comment(linker, "/STACK:102400000,102400000") /** 题目：hdu6078 Wavel Sequence 链接：http://acm.hdu.edu.cn/showproblem.php?pid=6078 题意：给定a序列和b序列。从a中取一个子序列x（数的位置顺序保持不变），子序列每个数满足a1<a2>a3<a4>a5<a6... 波浪形 从b中取相同长度的子序列y，也满足波浪形。 如果x与y序列一模一样，那么找到一个匹配方式。 求a与b两个序列有多少种匹配方式（相同的数但不同的位置，那么算作不同）。 思路： 定义dp[i][j][k]表示x序列以a[i]为结尾，y序列以b[j]结尾，k=0表示a[i]是波谷，k=1表示a[i]是波峰时候的匹配方式。 容易想到 dp[i][j][0] = sigma(dp[x][y][1]), x<i,y<j,b[x]>b[i]; （a[i]==b[j],a[x]==b[y]） dp[i][j][1] = sigma(dp[x][y][0]), x<i,y<j,b[x]<b[i]; 由于i的枚举是最外围循环，所以当前这个i要得到的结果来源前面计算过的，一定满足x<i.所以x<i不用作为限制因素。 现在要考虑满足y<j,b[x]>b[i]||b[x]<b[i]; 所以用二维树状数组维护y和b[x]。 定义c[j][value][k]表示y序列的结尾下标在j以内，数值大小value以内，波浪状态为k时候的匹配方式数。 */ #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<vector> #include<queue> #include<set> #include<cstring> #include<time.h> #include<random> #include<cmath> using namespace std; typedef pair<int,int> P; typedef long long LL; const int mod = 998244353; const int INF = 0x3f3f3f3f; const int N = 2005; int n, m; int a[N], b[N]; int dp[N][2]; int c[N][N][2]; ///二维树状数组 int query(int i,int j,int flag) { int s = 0; for(int x = i; x > 0; x-=(x&(-x))){ for(int y = j; y > 0; y-=(y&(-y))){ s = (s+c[x][y][flag])%mod; } } return s; } void update(int i,int j,int flag,int d) { for(int x = i; x <= 2000; x+=(x&(-x))){ for(int y = j; y <= 2000; y+=(y&(-y))){ c[x][y][flag] = (c[x][y][flag]+d)%mod; } } } int main() { int T; cin>>T; for(int i = 0; i<T; i++) { 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]); memset(c, 0, sizeof c); LL ans = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(a[i]!=b[j]) continue; dp[j][0] = (query(j,2000,1)-query(j,b[j],1)+1+mod)%mod;///+1是因为每一个b[j]都可以单独自身作为波谷，成为一个序列。 dp[j][1] = query(j,b[j]-1,0); ans = (ans+dp[j][0]) %mod; ans = (ans+dp[j][1]) %mod; update(j,b[j],0,dp[j][0]); update(j,b[j],1,dp[j][1]); } } printf("%lld ",ans); } return 0; }