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 a1<a2>a3<a4>a5<a6...

Picture from Wikimedia Commons

Now given two sequences a1,a2,...,an and b1,b2,...,bm, Little Q wants to find two sequences f1,f2,...,fk(1≤fi≤n,fi<fi+1) and g1,g2,...,gk(1≤gi≤m,gi<gi+1), where afi=bgi always holds and sequence af1,af2,...,afk is ''wavel''.

Moreover, Little Q is wondering how many such two sequences f and g he can find. Please write a program to help him figure out the answer.

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.

In each test case, there are 2 integers n,m(1≤n,m≤2000) in the first line, denoting the length of a and b.

In the next line, there are n integers a1,a2,...,an(1≤ai≤2000), denoting the sequence a.

Then in the next line, there are m integers b1,b2,...,bm(1≤bi≤2000), denoting the sequence b.

Output

For each test case, print a single line containing an integer, denoting the answer. Since the answer may be very large, please print the answer modulo 998244353.

Sample Input

1
3 5
1 5 3
4 1 1 5 3

Sample Output

Hint

(1)f=(1),g=(2).
(2)f=(1),g=(3).
(3)f=(2),g=(4).
(4)f=(3),g=(5).
(5)f=(1,2),g=(2,4).
(6)f=(1,2),g=(3,4).
(7)f=(1,3),g=(2,5).
(8)f=(1,3),g=(3,5).
(9)f=(1,2,3),g=(2,4,5).
(10)f=(1,2,3),g=(3,4,5).

题解：

　　设定dp[i][j][0/1] 表示已a[i], a[j]结尾的序列，长度为奇数1，偶数0的方案数

　　假设当前a[i] = a[j] = x；

　　那么dp[i][j][1]就要继承满足尾端值比当前x大的那些位置的那些dp[i'][j'][0] (1<=i' < i && 1<=j' < j)

　　同理dp[i][j][0] 就要继承满足结尾值比x小的那些 dp[i'][j'][1] 1<=i' < i && 1<=j' < j

　　定义树状数组sum[i][0] 表示以i值结尾的长度为奇数偶数的方案

　　在树状数组上面修改查询即可

代码：

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

typedef unsigned long long ULL;

const long long INF = 1e18+1LL;

const double pi = acos(-1.0);

const int N = 2e5+, M = 1e3+,inf = 2e9;

inline LL read()

{

    LL x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const LL mod = 998244353LL;

int n,m,a[N],b[N];

int nex[N],head[N],last[N],fi[N],vis[N],mx;

LL sum[N][],dp[][][];

void update(int x,LL c,int p) {

    for(int i = x; i <= mx; i += i&(-i))

        sum[i][p] += c,sum[i][p] %= mod;

}

LL ask(int x,int p) {

    LL ret = ;

    if(x == ) return ;

    for(int i = x; i; i -= i&(-i))

        ret += sum[i][p],ret %= mod;

    return ret;

}

int main() {

    int T;

    T = read();

    while(T--) {

        n = read();

        m = read();

        mx = -;

        for(int i = ; i <= n; ++i) a[i] = read(),mx = max(mx,a[i]);

        for(int i = ; i <= m; ++i) b[i] = read(),mx = max(mx,b[i]);

        for(int i = ; i <= n; ++i)

            for(int j = ; j <= m;++j)

                for(int k = ; k < ; ++k)

                    dp[i][j][k] = ;

        LL ans = ,tmp1,tmp2;

        for(int i = ; i <= n; ++i)

        {

            for(int j = ; j <= m; ++j)

                dp[i][j][] += dp[i-][j][],dp[i][j][] %= mod,

                dp[i][j][] += dp[i-][j][],dp[i][j][] %= mod;

            for(int j = ; j <= mx; ++j) sum[j][] = , sum[j][] = ;

            for(int j = ; j <= m; ++j) {

                if(a[i] == b[j]) {

                    tmp1 = ask(a[i]-,) % mod;

                    tmp2 = (ask(mx ,) - ask(a[i],) + mod) % mod;

                    dp[i][j][] += tmp1;

                    dp[i][j][] %= mod;

                    dp[i][j][] += (tmp2+1LL) % mod;

                    dp[i][j][] %= mod;

                    ans += ((tmp1+tmp2)%mod+1LL) % mod;

                    ans %= mod;

                }

                if(dp[i-][j][])

                    update(b[j],dp[i-][j][],);

                if(dp[i-][j][])

                    update(b[j],dp[i-][j][],);

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

HDU 6078 Wavel Sequence 树状数组优化DP

Wavel Sequence

最新文章

热门文章