E - Shuffle and Swap

Contest Duration: 2017-08-26(Sat) 12:00 - 2017-08-26(Sat) 14:30 (local time) (150 minutes) Back to Home

E - Shuffle and Swap Editorial

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$ で割った余りを出力せよ。

入力例 1Copy

Copy

1010
1100

出力例 1Copy

Copy

最初の二つのステップで、 $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$ となります。

入力例 2Copy

Copy

01001
01001

出力例 2Copy

Copy

$A$ の要素の入れ替えによって $A$ が変化することはなく、したがって必ず $A = B$ となります。

入力例 3Copy

Copy

101010
010101

出力例 3Copy

Copy

三回の $A$ の要素の入れ替えがどのように起こっても、 $A$ に含まれる $1$ は適切な位置に移動します。

入力例 4Copy

Copy

1101011011110
0111101011101

出力例 4Copy

Copy

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 1Copy

Copy

1010
1100

Sample Output 1Copy

Copy

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 2Copy

Copy

01001
01001

Sample Output 2Copy

Copy

No swap ever changes $A$ , so we'll always have $A = B$ .

Sample Input 3Copy

Copy

101010
010101

Sample Output 3Copy

Copy

Every possible sequence of three swaps puts the $1$ 's in $A$ into the right places.

Sample Input 4Copy

Copy

1101011011110
0111101011101

Sample Output 4Copy

Copy

932171449