No.2788 4-33 Hard
タグ : / 解いたユーザー数 21
作問者 :
YY-otter
/ テスター :
👑 
p-adic
簡単なストーリー
草野球チーム「斑点グラスホッパー」のファンである夜佐三さんは、試合での点数を各回ごとにカードに記録して保存しています。
ある日、夜佐三さんはカードを入れていたファイルをうっかりひっくり返してしまいました。
ひっくり返した時に $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$ で割った余りを出力してください。
Easy版からの変更点
夜佐三さんはファイルから飛び出したカードの枚数があまりにも多いことに気付いたため、カードに書かれた情報ごとに以下のように枚数を記録しました。
- $O_{a,b}$ は下部に
Xが含まれておらず、上部に $a$ 、下部に $b$ と書かれているカードの枚数 - $X_{a,b}$ は下部に
Xが含まれており、上部に $a$ 、下部からXを取り除くと $b$ と書かれているカードの枚数 - ただし、下部から
Xを取り除くと文字列が空になる場合は $b=0$ として扱う
入力
$O_{0,0}\ O_{0,1}\ \dots\ O_{0,33}$
$O_{1,0}\ O_{1,1}\ \dots\ O_{1,33}$
$\vdots$
$O_{4,0}\ O_{4,1}\ \dots\ O_{4,33}$
$X_{0,0}\ X_{0,1}\ \dots\ X_{0,33}$
$X_{1,0}\ X_{1,1}\ \dots\ X_{1,33}$
$\vdots$
$X_{4,0}\ X_{4,1}\ \dots\ X_{4,33}$
- $0\leq O_{a,b},\ X_{a,b}\leq 10^{18}\ (0\leq a\leq 4,\ 0\leq b\leq 33)$
- 入力は全て整数
出力
答えを $998244353$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
0 1 2 0 1 0 0 1 1 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 1 1 0 0 0 0 0 1 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 1 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 1 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 1 0 0 0 0 1 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 1 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 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
出力
4
サンプル1~3はEasy版のサンプル1~3をHard版の入力に変換したものです。
サンプル2
入力
71 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 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 0 0 0 0 0 0 0 0 1 1 8 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 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 0 0 0 0 0 0 0 0
出力
331646352
答えは非常に大きくなる可能性があるため、答えを $998244353$ で割った余りを出力してください。
サンプル3
入力
26 8 4 1 1 2 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 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 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 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 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 0 0 0 0
出力
228
サンプル4
入力
8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 8589934592 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
出力
762023815
入力値が32bit整数型に収まらないこともあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。