問題一覧 > 通常問題

No.2783 4-33 Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : YY-otterYY-otter / テスター : 👑 p-adicp-adic
1 ProblemId : 11022 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-14 12:10:45

簡単なストーリー

草野球チーム「斑点グラスホッパー」のファンである夜佐三さんは、試合での点数を各回ごとにカードに記録して保存しています。
ある日、夜佐三さんはカードを入れていたファイルをうっかりひっくり返してしまいました。
ひっくり返した時に $N$ 枚のカードがファイルから飛び出してしまったので、飛び出したカードの中から $9$ 枚を拾ったところ、適切に並び替えることで試合結果が $4-33$ となる組み合わせであることに気付きました。
飛び出したカードの中からこのような組み合わせになる拾い方が何通りあるのか気になった夜佐三さんのために、実際に何通りあるのか求めてあげてください。

問題文

$N$ 枚のそれぞれ区別できるカードの情報が与えられます。$i$ 枚目のカードには、上部に $A_i$ 、下部に $B_i$ と書かれています。
$A_i$ は非負整数、$B_i$ は非負整数、X(大文字)、正整数(の十進法表記)の後ろにXを繋げた文字列のいずれかです。
$N$ 枚のカードの中から良いスコアボードが存在するような $9$ 枚のカードを選びます。
良いスコアボードとは、以下の条件を満たす $9$ 枚のカードの並べ方です。


良いスコアボードの条件:

  • 横一列にカードを並べ、左から $j\ (1\leq j\leq 9)$ 枚目のカードの上部に $U_j$ 、下部に $D_j$ と書かれているとする
  • $1\leq j\leq 8$ において $D_j$ はXを含まない
  • 以下、$D_9$ からXを除けるだけ除いた文字列を整数と見て $d_9$ とする(ただし、文字列が空になる場合は $d_9=0$ とする)
  • $\displaystyle\sum_{k=1}^9U_k<\sum_{k=1}^8D_k+d_9$ ならば $D_9$ はXを含み、かつ $d_9\neq0$ ならば $\displaystyle\sum_{k=1}^9U_k\geq \sum_{k=1}^8D_k+d_9-4$


良いスコアボードが存在するような $9$ 枚のカードの選び方のうち、上部の合計が $4$ 、下部の合計が $33$ になるような選び方は何通りあるか求めてください。
正確には、$\displaystyle\sum_{k=1}^9U_k=4,\ \displaystyle\sum_{k=1}^8D_k+d_9=33$ を満たすような良いスコアボードが存在する $9$ 枚のカードの選び方の通り数を求めてください。
ただし、答えは非常に大きくなる可能性があるため、答えを $998244353$ で割った余りを出力してください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_N$

  • $9\leq N\leq 2000$
  • $0\leq A_i\leq 4$
  • $0\leq B_i\leq 33$ もしくは $B_i=$X(大文字)もしくは $B_i$ は $1\leq b\leq 33$ を満たす整数(の十進法表記)の後ろにXを繋げた文字列
  • 入力の数値は全て整数

出力

答えを $998244353$ で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
14
1 0 1 0 0 2 0 1 0 3 0 0 1 0
2 7 1 8 2 8 1 8 2 8 4 5X 9X X
出力
4

例えば $i=1,2,3,4,5,6,7,11,14$ 枚目や $i=1,2,3,4,6,7,9,11,14$ 枚目を選んだとき、この順に並べると以下の図のようになります。





どちらも良いスコアボードの条件を満たし、上部の合計が $4$ 、下部の合計が $33$ になっているため条件を満たします。
$5$ 枚目と $9$ 枚目に区別があることに注意してください。

サンプル2
入力
81
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
33 0 0 0 0 0 0 0 X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X 0 0 0 0 0 0 0 0 1X
出力
331646352

答えは非常に大きくなる可能性があるため、答えを $998244353$ で割った余りを出力してください。

サンプル3
入力
52
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 1 5X 1 1 0 0 0 5 0 3 X 0 1 0 2 0 0 7 0 0 0 2 0 1 0 0 0 0 0 0 7 1 10 2 0 0 1 X 5 4 0 1 0 0 0 2 X
出力
228

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。