|
||||||||||
Sakurada ResetTime Limit: 15000/12000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 142 Accepted Submission(s): 17 Problem Description A huge revolution is coming up in Sakurada. In order to avoid the revolution, Asai Kei is going to take some actions. The director of the revolution will also take some actions to defend Asai Kei. In this problem, each action can be described as a positive integer. Specifically, Asai Kei will choose a non-empty subsequence as the actual actions to take from a given sequence a. Meanwhile, the director will similarly choose a non-empty subsequence as the defending actions from a given sequence b. And the influence value of a sequence of actions p1, p2, ¡¤ ¡¤ ¡¤ , pk of length k is defined as follows: Now given action sequences a and b, Asai Kei will choose a non-empty subsequence A from a and the director will choose a non-empty subsequence B from b. Asai Kei can beat the director if and only if the influence value of A is strictly greater than B. You want to know the number of different schemes for them to choose subsequences A and B so that Asai Kei can beat the director. Two schemes (A1, B1),(A2, B2) are considered to be different if A1 = A2 or B1 = B2, and two sequences p, q are considered to be different if their influence values are different. Print the answer modulo 998244353 in a single line. Input The first line contains two positive integers n, m (1 ¡Ü n, m ¡Ü 5 000), denoting the length of a and the length of b. The next line contains n positive integers ai (1 ¡Ü ai ¡Ü 100), denoting the sequence a. The next line contains m positive integers ai (1 ¡Ü bi ¡Ü 100), denoting the sequence b. Output Output a single line containing a non-negative integer, denoting the answer modulo 998244353. Sample Input
Sample Output
Hint Asai Kei can choose 6 subsequences: (1), (2), (1,2), (2,1), (2,2), (2,1,2), and their influence values are 1, 2, 1002, 2001, 2002, 2001002 respectively. The director can choose 11 subsequences: (1), (2), (1,1), (1,2), (2,1), (2,2), (1,1,2), (1,2,1), (1,2,2), (2,1,2), (2,2,2), and their influence values are 1, 2, 1001, 1002, 2001, 2002, 1001002, 1002001, 1002002, 2001002, 2002002 respectively. There are 0 + 1 + 3 + 4 + 5 + 9 = 22 schemes in total that Asai Kei can beat the director. Source | ||||||||||
|