P10011 [CTT Mutual Test 2023] Counting Maximum Flows on a Grid Graph

Given $n, m, k$, two positive integer sequences $a_{1...n}, b_{1...m}$, and a $k \times k$ $01$ matrix $s_{1...k,1...k}$. Consider a directed graph $G=(V,E)$, where $V=\{S,T\}\cup(\{0,1\}\times ([1,k]\cap\mathbb{Z})^2)$, and $E=E_1\cup E_2\cup E_3$ consists of three parts: - $E_1=\{(S,(0,1,a_i)) \mid 1\le i\le n\}\cup\{((1,k,b_i),T)\mid 1\le i\le m\}$ - $E_2=\{((1,i,j),(0,i+1,j))\mid1\le i

The first line contains three positive integers $n, m, k$. The second line contains $n$ positive integers $1\le a_1

Output one line with two non-negative integers, representing the maximum flow and the number of maximum flows, respectively. The latter should be taken modulo $10^9+7$.

The sample is provided in the attached file. For all testdata, $1\le n,m\le k\le400$. | Subtask ID | $n\le$ | $k\le$ | Special Property | Subtask Score | | :--------: | :----: | :----: | :--------------: | :-----------: | | $1$ | $7$ | $7$ | None | $5$ | | $2$ | $18$ | $18$ | None | $5$ | | $3$ | $10$ | $400$ | None | $10$ | | $4$ | $100$ | $400$ | None | $25$ | | $5$ | $400$ | $400$ | $n=m$ and the maximum flow is $n$ | $10$ | | $6$ | $400$ | $400$ | The maximum flow is $n$ | $25$ | | $7$ | $400$ | $400$ | None | $20$ | Translated by ChatGPT 5