AT_arc136_f [ARC136F] Flip Cells

[problemUrl]: https://atcoder.jp/contests/arc136/tasks/arc136_f $ H $ 行 $ W $ 列からなる盤面があり，各マスには `0` か `1` が書き込まれています． 盤面の状態は $ H $ 個の文字列 $ S_1,S_2,\cdots,S_H $ で表され， $ S_i $ の $ j $ 文字目が，上から $ i $ 行目，左から $ j $ 列目のマスに書かれている数字を表します． すぬけくんはこれから，次の操作を繰り返します． - 一つのマス目を一様ランダムに選ぶ． そして，そのマス目に書かれている値を flip する．（つまり，`0` ならば `1` に変え，`1` ならば `0` に変える） ところで，すぬけ君は整数列 $ A=(A_1,A_2,\cdots,A_H) $ が大好きです． そのため，以下の条件が満たされた瞬間，操作を終了します． - すべての $ i $ ($ 1\ \leq\ i\ \leq\ H $) について，$ i $ 行目にある `1` の個数がちょうど $ A_i $ である． 特に，操作を $ 0 $ 回しか行わないこともありえます． すぬけくんが行う操作回数の期待値を $ \text{mod\ }{998244353} $ で求めてください． 期待値 $ \text{mod\ }{998244353} $ の定義 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、$ Q\ \not\ \equiv\ 0\ \pmod{998244353} $ となることも証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ &lt\ 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

N/A

N/A

### 制約 - $ 1\ \leq\ H,W\ \leq\ 50 $ - $ S_i $ は `0`, `1` からなる長さ $ W $ の文字列 - $ 0\ \leq\ A_i\ \leq\ W $ ### Sample Explanation 1 操作の様子は以下のようになります． - 確率 $ 1/2 $ で `1` の書かれたマスを flip する．$ 1 $ 行目にある `1` の個数が $ 0 $ になり，操作が終了する． - 確率 $ 1/2 $ で `0` の書かれたマスを flip する．$ 1 $ 行目にある `1` の個数は $ 2 $ になり，操作は継続する． - いずれかのマスを flip する．flip したマスに依らず，$ 1 $ 行目にある `1` の個数は $ 1 $ になり，操作は継続する． - 確率 $ 1/2 $ で `1` の書かれたマスを flip する．$ 1 $ 行目にある `1` の個数が $ 0 $ になり，操作が終了する． - 確率 $ 1/2 $ で `0` の書かれたマスを flip する．$ 1 $ 行目にある `1` の個数は $ 2 $ になり，操作は継続する． - $ \vdots $ 操作回数の期待値は $ 3 $ になります．