← 返回题目列表

AtCoder · agc019_e

E. 随机播放和交换

中文机器翻译题面 查看原题

分数: 1700 点

问题陈述

你有两个字符串 A = A_1 A_2 ... A_n 和 B = B_1 B_2 ... B_n 相同长度的组成 0 和 1。 数量 1位于 A 和 B 相等。

你已经决定转型 A 使用以下算法:

  • 让 a_1, a_2, ..., a_k 是指数 1位于 A.
  • 让 b_1, b_2, ..., b_k 是指数 1位于 B.
  • 替换 a 和 b 及其随机排列,独立且统一地选择。
  • 对于每个 i 来自 1 to k,按顺序,交换 A_{a_i} 和 A_{b_i}.

让 P 是字符串的概率 经过上述过程后, A 和 B 变得相等。

让 Z = P \times (k!)^2。显然, Z 是一个整数。

查找 Z 模数 998244353.

约束

  • 1 \leq |A| = |B| \leq 10,000
  • A 和 B 包括 0 和 1.
  • A 和 B 包含相同数量的 1的。
  • A 和 B 包含至少一个 1.

部分分数

  • 1200 通过满足以下条件的测试集将获得积分 1 \leq |A| = |B| \leq 500.

输入

输入由标准输入按以下格式给出:

A
B

输出

打印以下值 Z 模数 998244353.


示例输入 1

1010
1100

示例输出 1

3

前两步之后, a = [1, 3] 和 b = [1, 2]。有 给出的 4 洗牌后可能出现的情况 a 和 b:

  • a = [1, 3], b = [1, 2]。最初, A = 1010。交换后(A_1, A_1), A = 1010。交换后(A_3, A_2), A = 1100.
  • a = [1, 3], b = [2, 1]。最初, A = 1010。交换后(A_1, A_2), A = 0110。交换后(A_3, A_1), A = 1100.
  • a = [3, 1], b = [1, 2]。最初, A = 1010。交换后(A_3, A_1), A = 1010。交换后(A_1, A_2), A = 0110.
  • a = [3, 1], b = [2, 1]。最初, A = 1010。交换后(A_3, A_2), A = 1100。交换后(A_1, A_1), A = 1100.

超出 4 场景, 3 其中导致 A = B。因此, P = 3 / 4,和 Z = 3.


示例输入 2

01001
01001

示例输出 2

4

交换从未改变 A,所以我们总是有 A = B.


示例输入 3

101010
010101

示例输出 3

36

三个交换的每个可能序列都将 1位于 A 进入正确的地方。


示例输入 4

1101011011110
0111101011101

示例输出 4

932171449