問題一覧 > 通常問題

No.1771 A DELETEQ

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 46
作問者 : SPD_9X2 / テスター : 👑 hitonanode
お気に入りにしたユーザー ProblemId : 7125 / 自分の提出
問題文最終更新日: 2021-12-02 21:44:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

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$
If you are not attempting the evil cases, making your program terminate immediately when the input does not satisfy the normal constraints will make the judging finish sooner.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。