No.2788 4-33 Hard
YY-otter
p-adicBrief Story
Yasazo, a fan of the amateur baseball team "Spotted Grasshoppers", records the score of each inning of their games on cards and keeps them.
One day, Yasazo accidentally turned over the file holding the cards.
When the file was turned over, $N$ cards fell out of it. Yasazo picked up $9$ of the cards that fell out and noticed that they form a combination which, when arranged appropriately, gives a game result of $4-33$.
Yasazo now wonders how many ways there are to pick up such a combination from the cards that fell out. Please find the actual number of ways.
Problem Statement
You are given information about $N$ mutually distinguishable cards. The $i$-th card has $A_i$ written on its top part and $B_i$ written on its bottom part.
$A_i$ is a non-negative integer, and $B_i$ is one of the following: a non-negative integer, X (uppercase), or a string formed by appending X to (the decimal representation of) a positive integer.
Choose $9$ of the $N$ cards such that a good scoreboard exists for them.
A good scoreboard is an arrangement of the $9$ cards that satisfies the following conditions.
Conditions for a good scoreboard:
- Arrange the cards in a horizontal row, and let $U_j$ be written on the top part and $D_j$ on the bottom part of the $j\ (1\leq j\leq 9)$-th card from the left
- For $1\leq j\leq 8$, $D_j$ does not contain
X - Below, let $d_9$ be the string obtained by removing from $D_9$ as many
Xas possible, regarded as an integer (if the string becomes empty, let $d_9=0$) - If $\displaystyle\sum_{k=1}^9U_k<\sum_{k=1}^8D_k+d_9$, then $D_9$ contains
X, and if $d_9\neq0$, then $\displaystyle\sum_{k=1}^9U_k\geq \sum_{k=1}^8D_k+d_9-4$
Among the ways to choose $9$ cards such that a good scoreboard exists, find the number of ways for which the sum of the top parts is $4$ and the sum of the bottom parts is $33$.
More precisely, find the number of ways to choose $9$ cards such that there exists a good scoreboard satisfying $\displaystyle\sum_{k=1}^9U_k=4,\ \displaystyle\sum_{k=1}^8D_k+d_9=33$.
Since the answer can be very large, output the answer modulo $998244353$.
Changes from the Easy Version
Yasazo noticed that far too many cards had fallen out of the file, so the number of cards was recorded for each kind of information written on them, as follows.
- $O_{a,b}$ is the number of cards whose bottom part does not contain
X, with $a$ written on the top part and $b$ written on the bottom part - $X_{a,b}$ is the number of cards whose bottom part contains
X, with $a$ written on the top part and $b$ written on the bottom part after removingX - However, if removing
Xfrom the bottom part makes the string empty, it is treated as $b=0$
Input
$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)$
- All inputs are integers
Output
Output the answer modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
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
Output
4
Samples 1~3 are Samples 1~3 of the Easy version converted to the input format of the Hard version.
Sample 2
Input
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
Output
331646352
Since the answer can be very large, output the answer modulo $998244353$.
Sample 3
Input
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
Output
228
Sample 4
Input
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
Output
762023815
Input values may not fit in a 32-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。