No.767 The Japari Buns That Were Handed Out
タグ : / 解いたユーザー数 29
作問者 :
This problem may serve as a hint.
Problem Statement
You are now in an area called a "chihou" of a zoo called Japari Park.
This chihou is represented as a grid measuring $H$ meters vertically and $W$ meters horizontally, consisting of $(H+1)\times(W+1)$ lattice points. The top-left lattice point is $(0,0)$ and the bottom-right lattice point is $(H,W)$.
In this chihou there are $K$ animals in human form called Friends, and the $i$-th Friend is known to be at $(a_i, b_i)$. Also, at most $1$ Friend is at any one location.
You cannot pass through a location where a Friend is, but you become able to pass through it if you give that Friend a steamed bun called a Japari bun.
There are no Friends at the start or the goal.
You are now at $(0,0)$ and are going to $(H,W)$ moving only right or down.
You are curious about the number of paths to $(H,W)$ moving only right or down.
For various ways of giving out Japari buns, find the number of paths to $(H,W)$ moving only right or down.
You are given $2^K$ queries.
In the $i$-th (1-indexed) query, if the $j$-th (1-indexed) digit from the bottom of the binary representation of $i-1$ is 0, you give a Japari bun to the $j$-th Friend in that query; if it is 1, you do not give a Japari bun to the $j$-th Friend in that query.
For each query, output the number of paths to $(H,W)$ moving only right or down when Japari buns are given out in the way that query represents, modulo $10^8+7$.
If there is no path to $(H,W)$, output $0$.
Input
$H$ $W$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_K$ $b_K$
$H$ and $W$ represent the vertical and horizontal lengths of this chihou, respectively.
$K$ represents the number of Friends in this chihou.
$a_i,b_i$ represent that the $i$-th Friend is at $(a_i,b_i)$.
$1≤H,W≤10^5$
$1≤K≤min(20, (H + 1) (W + 1) - 2)$
$0≤a_i≤H$
$0≤b_i≤W$
$(a_i, b_i)≠(a_j, b_j)$ when $i≠j$
However, it is possible for just one of $a,b$ to coincide
$(a_i, b_i) \ne (0,0),(H,W)$
(There are no Friends at the start or the goal)
Output
Output $2^K$ lines. On the $i$-th line, output the answer to the $i$-th query.
Note that the output is large, up to about 1 million lines.
Sample
Sample 1
Input
1 2 1 0 1
Output
3 1
If you give a Japari bun to Friend $1$, there are $3$ paths: down-right-right, right-down-right, and right-right-down.
If you do not give a Japari bun to Friend $1$, there is $1$ path: down-right-right.
s-1-o | | | o-o-g
Sample 2
Input
3 3 2 2 1 1 2
Output
20 11 11 2
s-o-o-o | | | | o-o-2-o | | | | o-1-o-o | | | | o-o-o-g
Sample 3
Input
3 3 4 1 0 1 1 1 2 1 3
Output
20 10 8 4 11 4 5 1 16 7 6 2 10 3 4 0
s-o-o-o | | | | 1-2-3-4 | | | | o-o-o-o | | | | o-o-o-g
Sample 4
Input
20 18 5 4 9 18 2 3 10 18 8 17 10
Output
77998265 17271238 77969195 17242168 68667836 7940809 68638766 7911739 74888122 14161095 74871592 14144565 65557693 4830666 65541163 4814136 86011338 26935961 85982268 26906891 76728099 17652722 76699029 17623652 82901195 23825818 82884665 23809288 73617956 14542579 73601426 14526049
Don't forget to take the result modulo $10^8+7$.
Sample 5
Input
3000 3000 10 685 339 1255 1743 1838 961 668 2662 2688 1546 1675 1056 2953 2056 196 460 1990 955 243 2303
Output
41851678 88930621 75240276 13062597 90869769 72043296 24258360 96175279 79892182 26971118 13280773 51103101 ... (長いので省略) 33023592 38873219 93287621 95644688 78014337 89484964 66543267 63279334 51269983 57119610
Sample 6
Input
70000 90000 16 65133 3336 12082 88737 57559 1709 2660 8526 30136 27968 34819 40321 8688 26480 6491 65230 37371 69584 1876 13309 63014 1937 69427 8281 1355 77227 57115 1528 935 14747 61758 57582
Output
15709191 85308639 86356296 55955737 24627065 24785722 95274170 95432827 13298101 82897549 57412092 27011533 22215975 22374632 ... (長いので省略)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。