No.1771 A DELETEQ
タグ : / 解いたユーザー数 46
作問者 :
SPD_9X2
/ テスター :
👑
hitonanode
Note
A harder version of this problem exists: Many DELETEQs. Note that its input and output formats are different.
Problem Statement
You have $x$ copies of the string "AB" and $y$ copies of the string "BA".
You arrange all of these $x+y$ strings in any order you like and concatenate them. (Let $S$ be the resulting string.) Then, you perform the following operation any number of times, $0$ or more.
- Choose a pair of adjacent $2$ characters in $S$ that are equal, and delete the chosen $2$ characters from $S$. Then, concatenate the remaining parts before and after them, keeping their original order.
How many different strings are possible as the string $S$ remaining after the operations? Find the count modulo $998244353$.
If the string $S$ after the operations can be the empty string, the empty string is also counted as $1$ possibility.
Input
$x\ y$
The normal constraints of this problem are as follows. If your program is correct on all test cases satisfying these constraints, the verdict will be AC.
- All inputs are integers.
- $1 \le x \le 4000$
- $1 \le y \le 4000$
This problem also has high-difficulty constraints, provided as evil cases that are unrelated to the AC verdict. If you have the energy to spare, please give them a try. (I think they are harder than Many DELETEQs.)
The constraints of the evil cases are as follows.
- All inputs are integers.
- $1 \le x \le 10^5$
- $1 \le y \le 10^9$
Output
Print the answer on $1$ line. Add a newline at the end.
Sample
Sample 1
Input
1 1
Output
5
"ABBA"
"BAAB"
"AA" (obtainable by "ABBA" → "AA")
"BB" (obtainable by "BAAB" → "BB")
"" (obtainable by "ABBA" → "AA" → "")
These $5$ strings are possible.
Sample 2
Input
3 1
Output
11
Sample 3
Input
4000 4000
Output
622937044
Print the count modulo $998244353$.
Sample 4 (evil case only)
Input
100000 1000000000
Output
825008896
This test case is included only in the evil cases, which are unrelated to the AC verdict.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。