题
OvO http://acm.hdu.edu.cn/showproblem.php?pid=6078
(2017 Multi-University Training Contest - Team 4 - 1012)
解
记f[i][j][k]为在s1中以第i位结尾，s2中以第j为结尾，末端状态（上升为1，下降为0）为k的子序列的个数
则f[i][j][k]=∑f[p][q][1-k] (p<i,q<j，而且新加入的点要使原序列结尾状态发生变化)
可见这是和矩阵差不多的东西
可以把这个当做一个矩形，s1竖着，s2横着
然后用类似前缀和的思想来优化
有2个数组用于优化
fx[i][j][k]代表，状态k时，第1~i行，第j列的综合，即第j列的前缀。每当(i,j)处产生新方案的时候，都要往(i+1,j)处更新
fy[i][j][k]比较特殊，代表状态k时，第i行第j列可行的方案数量，也就是可以直接用于(i,j)点更新的方案数量。
fy的数组的更新的话
1.对于同一行的fy[i][j][k]直接向后推至fy[i][j+1][k]处
2.对于fx[i][j][k]中的方案，如果合法，则放入该行的fy[i][j+1][k]中。
对于合法的判断，由于fx[i][j][k]中的方案，对于s2上的数，是以s2[j]结尾的，而当前这一行的要更新的点，对应的是s1[i]。也就是说根据k的值将两者比较就可以判断是否合法。
维护这两个数组，如果当前点s1[i]==s2[j]就代表可以把fy中预备着的值（实质上是一个二维的前缀和）加入到答案中来。每次更新答案都会产生新的序列，要把这个序列的数量放到fx中。
（思路来自csy的标程与题解）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring> using namespace std; typedef long long ll; const int M=2044;
const ll mod=998244353; int n,m;
ll fx[M][M][2],fy[M][M][2];//if the tail of is up 1, otherwise 0
int s1[2222],s2[2222]; void init()
{
memset(fx,0,sizeof(fx));
memset(fy,0,sizeof(fy));
} void solve()
{
//regard it as a matrix
//s1 row ; s2 col
int i,j,k;
ll ans=0,tmp;
for(i=1;i<=n;i++) //row
for(j=1;j<=m;j++) //col
for(k=0;k<=1;k++)
{
if(s1[i]==s2[j]) //new seq
{
tmp=fy[i][j][1-k];
if(k)
tmp++;
if(tmp)
{
ans=(ans+tmp)%mod;
fx[i+1][j][k]=(fx[i+1][j][k]+tmp)%mod; //push up the num of new seq
}
} //fx push up
fx[i+1][j][k]=(fx[i+1][j][k]+fx[i][j][k])%mod;
if((k && s1[i]>s2[j]) || (!k && s1[i]<s2[j])) //if the fx have affect on this row
fy[i][j+1][k]=(fy[i][j+1][k]+fx[i][j][k])%mod; //fy push up
fy[i][j+1][k]=(fy[i][j+1][k]+fy[i][j][k])%mod;
}
cout<<ans<<endl;
} int main()
{
int T,i,j;
cin>>T;
while(T--)
{
init();
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&s1[i]);
for(i=1;i<=m;i++)
scanf("%d",&s2[i]);
solve();
}
return 0;
}