分数: 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