問題一覧 > 通常問題

No.767 The Japari Buns That Were Handed Out

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : ミドリムシ
お気に入りにしたユーザー ProblemId : 2247 / 自分の提出
問題文最終更新日: 2021-08-20 15:53:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:
This is the problem for day 15 of Advent Calendar Contest 2018.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。