/ 
Time Limit: 2 sec / Memory Limit: 512 MB
配点 : 1700 点
問題文
0 と 1 からなる同じ長さの二つの文字列 A = A_1 A_2 ... A_n と B = B_1 B_2 ... B_n があります。 A, B に含まれる 1 の個数は等しいです。
あなたは次のアルゴリズムによって A を変化させることにしました。
- a_1, a_2, ..., a_k を、A で 1 が出現する位置の添字とする。
- b_1, b_2, ..., b_k を、B で 1 が出現する位置の添字とする。
- a, b の要素をそれぞれ無作為に並び替える。これらの無作為な並び替えは一様かつ独立である。
- 1 から k までの各 i に対して、順に A_{a_i} と A_{b_i} の値を入れ替える。
この手順のあと、文字列 A, B が一致する確率を P とします。
さらに、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 が少なくとも一つ含まれる。
部分点
- 1 \leq |A| = |B| \leq 500 を満たすデータセットに正解すると、1200 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
Z を 998244353 で割った余りを出力せよ。
入力例 1
1010 1100
出力例 1
3
最初の二つのステップで、a = [1, 3], b = [1, 2] となります。a, b の要素を無作為に並び替えたあとの結果としてありうるものは次の 4 つです。
- 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 が変化することはなく、したがって必ず A = B となります。
入力例 3
101010 010101
出力例 3
36
三回の A の要素の入れ替えがどのように起こっても、A に含まれる 1 は適切な位置に移動します。
入力例 4
1101011011110 0111101011101
出力例 4
932171449
Score : 1700 points
Problem Statement
You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1. The number of 1's in A and B is equal.
You've decided to transform A using the following algorithm:
- Let a_1, a_2, ..., a_k be the indices of 1's in A.
- Let b_1, b_2, ..., b_k be the indices of 1's in B.
- Replace a and b with their random permutations, chosen independently and uniformly.
- For each i from 1 to k, in order, swap A_{a_i} and A_{b_i}.
Let P be the probability that strings A and B become equal after the procedure above.
Let Z = P \times (k!)^2. Clearly, Z is an integer.
Find Z modulo 998244353.
Constraints
- 1 \leq |A| = |B| \leq 10,000
- A and B consist of 0 and 1.
- A and B contain the same number of 1's.
- A and B contain at least one 1.
Partial Score
- 1200 points will be awarded for passing the testset satisfying 1 \leq |A| = |B| \leq 500.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the value of Z modulo 998244353.
Sample Input 1
1010 1100
Sample Output 1
3
After the first two steps, a = [1, 3] and b = [1, 2]. There are 4 possible scenarios after shuffling a and b:
- a = [1, 3], b = [1, 2]. Initially, A = 1010. After swap(A_1, A_1), A = 1010. After swap(A_3, A_2), A = 1100.
- a = [1, 3], b = [2, 1]. Initially, A = 1010. After swap(A_1, A_2), A = 0110. After swap(A_3, A_1), A = 1100.
- a = [3, 1], b = [1, 2]. Initially, A = 1010. After swap(A_3, A_1), A = 1010. After swap(A_1, A_2), A = 0110.
- a = [3, 1], b = [2, 1]. Initially, A = 1010. After swap(A_3, A_2), A = 1100. After swap(A_1, A_1), A = 1100.
Out of 4 scenarios, 3 of them result in A = B. Therefore, P = 3 / 4, and Z = 3.
Sample Input 2
01001 01001
Sample Output 2
4
No swap ever changes A, so we'll always have A = B.
Sample Input 3
101010 010101
Sample Output 3
36
Every possible sequence of three swaps puts the 1's in A into the right places.
Sample Input 4
1101011011110 0111101011101
Sample Output 4
932171449