問題文

すぬけ君は、店を開こうとしています。N 個の商品を販売する予定です。 i 番目の商品は、p_i 円で販売されます。

すぬけ君は、それぞれの価格の末尾についた 0 をたくさん書くのが大変に感じたので、 N 個全ての商品の値札の末尾に連続する 0 を全ての商品について同じ個数だけ取り除き、 会計の時にその分の 0 を補完することにしました。

商品の値札 1 枚あたり、 0 を最大何個取り除けるかを求めてください。

制約

• 1 ≤ N ≤ 100
• 1 ≤ p_i ≤ 10^9
• p_i は整数

入力例 1

4
300
250
6000
730

出力例 1

1

それぞれ、末尾についた 0 を 1 つだけ取り除くことができ、すると値札には 30, 25, 600, 73 と書かれることになります。

入力例 2

5
10000000
30000000
150000000
200000000
990000000

出力例 2

7

入力例 3

4
100101100
110010000
100001001
110011000

出力例 3

0

問題文

あなたはオンサイトコンテストの運営担当者です。 このコンテストの参加者は N 人おり、1, 2, ..., N の番号が付けられています。 参加者 i は x 軸上の座標 X_i の位置に住んでいます。

あなたはコンテストの参加者に会場までの交通費を支給することを検討しています。 参加者 i への支給額は、コンテスト会場の位置 c と基準値 d から以下のように定めることにしています。

• |X_i - c| \leq d のとき、|X_i - c| 円
• そうでないとき、d 円

会場の位置 c と基準値 d を定めるにあたって、Q 種類のこれらの値の候補に対して、参加者に支給する交通費の合計を計算することにしました。

整数 C_1, C_2, ..., C_Q および D_1, D_2, ..., D_Q が与えられます。 i = 1, 2, ..., Q に対して、c = C_i, d = D_i としたときの参加者に支給する交通費の合計を求めてください。

制約

• 1 \leq N \leq 10^5
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• X_i < X_{i + 1} (1 \leq i < N)
• 1 \leq Q \leq 10^5
• 0 \leq C_i, D_i \leq 10^9 (1 \leq i \leq Q)
• 入力値はすべて整数である。

入力例 1

5 3
1 5 10 20 30
7 3
10 20
100 10

出力例 1

14
44
50

たとえば、c の値を C_1 = 7 に、d の値を D_1 = 3 にした場合、 各参加者に交通費としてそれぞれ 3 円、2 円、3 円、3 円、3 円を支給することになります。 よって 1 行目には 3 + 2 + 3 + 3 + 3 =14 を出力します。

入力例 2

6 3
0 1 2 999999998 999999999 1000000000
0 0
100 99
1000000000 1000000000

出力例 2

0
593
3000000000

入力例 3

7 5
590 593 633 642 743 859 872
642 850108511
743 153
633 20
642 0
842 60895346

出力例 3

658
759
109
0
1056

問題文

( と ) からなる文字列 S が与えられます。次の条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組はいくつあるでしょうか。

条件: - S の i 文字目から j 文字目まで (両端を含む) を取り出した時、その文字列は括弧の対応が取れている。

括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

• 空文字列
• ある括弧の対応が取れている文字列 A, B が存在し、 A, B をこの順に連結した文字列
• ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列

制約

• 1 ≤ |S| ≤ 10^5
• S は (, ) のみからなる文字列

入力例 1

((())

出力例 1

2

• S の 2 文字目から 5 文字目までを取り出すと、 (()) です。これは括弧の対応が取れています。
• S の 3 文字目から 4 文字目までを取り出すと、 () です。これは括弧の対応が取れています。

よって、 (2, 5) および (3, 4) が条件を満たします。

入力例 2

(()()(())(

出力例 2

7

問題文

長さ N の 2 つの整数列 (A_1, A_2, ..., A_N), (B_1, B_2, ..., B_N) があります． あなたは，数列 A に対して次の操作を繰り返し行うことができます：

• 整数 i (1 \leq i \leq N-1) を選ぶ．そして，A_i を A_i xor A_{i+1} に置き換えるか，A_{i+1} を A_i xor A_{i+1} に置き換えるかのいずれかを行う．

ただし，xor はビットごとの排他的論理和を表します．

この操作を繰り返すことで，A と B を一致させることができるかを判定してください．

制約

• 1 \leq N \leq 100000
• A_i, B_i は整数
• 0 \leq A_i \leq 2^{60} - 1
• 0 \leq B_i \leq 2^{60} - 1

入力例 1

4
4 6 1 2
4 0 3 2

出力例 1

Yes

はじめ，A は (4, 6, 1, 2) です．

• i=2 を選んで，A_2 を A_2 xor A_3 で置き換えると，A は (4, 7, 1, 2) になります．
• i=1 を選んで，A_2 を A_1 xor A_2 で置き換えると，A は (4, 3, 1, 2) になります．
• i=3 を選んで，A_3 を A_3 xor A_4 で置き換えると，A は (4, 3, 3, 2) になります．
• i=2 を選んで，A_2 を A_2 xor A_3 で置き換えると，A は (4, 0, 3, 2) になります．

よって，A と B を一致させることができます．

入力例 2

5
1 1 1 1 1
2 2 2 2 2

出力例 2

No

どのように操作をしても，A と B を一致させることはできません．

入力例 3

10
9078757738433288 290842434722050 159090006056 289488767243292968 141906289967362 3848861155586 19265097448903424 5761445266577952 616899717105952 343731622434
546704308666859716 487893585065153542 489415167130509384 152982254363317262 324189516636095686 286066742397022348 90758284568626244 239298268501286990 196514071259067468 466853324654813188

出力例 3

No

入力例 4

12
377856130335197936 431521378213127644 96779183645318069 27884533191077098 175463727782485301 417798313887768470 882780118961099438 695638305642195413 844098458810131862 714758857685818365 982440320392901313 58851425009165345
200247916520409945 1079265167001944511 228890967431065270 594413217207808713 799020374004987514 1064838643421037658 816982417931746301 59262707979926837 802875123164857614 244683246935893681 50108983568402635 248665965512365971

出力例 4

Yes

問題文

(, ), +, -, *, a のみからなる数式 S が与えられます(詳細は問題文の後半を参照してください)。S に含まれる a の個数を N とします。

N 個の整数 a_1, ..., a_N と 2 個の整数 (b_i, x_i) からなる Q 個のクエリが与えられるので、これらのクエリを処理してください。

クエリ: 与えられた数式中の左から b_i 番目の a を x_i に、左から 1, ..., b_i-1, b_i+1, ..., N 番目の a をそれぞれ a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N に置き換えた数式の値と 10^9+7 を法として合同な 0 以上 10^9+6 以下の整数を出力する。

この問題で与えられる数式 S は、以下のような BNF 表記の <expr> シンボルで表されます。

<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')' 

制約

与えられる数式に含まれる a の個数を N とします。

• S の長さは 200\,000 以下
• S は問題文中の BNF 表記の <expr> シンボルとして表せる
• 0 ≤ a_i < 10^9+7
• 1 ≤ Q ≤ 10^5
• 1 ≤ b_i ≤ N
• 0 ≤ x_i < 10^9+7
• x_i は整数

入力例 1

(a-(a))*a
4
0 1 2
1 1
1 2
2 1
1 4

出力例 1

0
2
1000000005
6

例えば最初のクエリでは、左から 1 番目の a には x_1 = 1 が、左から 2 番目の a には a_2 = 1 が、左から 3 番目の a には a_3 = 2 を代入し、計算すると、 (1-(1))*2 = 0 となり、0 が答えです。

3 番目ののクエリでは、左から 1 番目の a には a_1 = 0 が、左から 2 番目の a には x_3 = 1 が、左から 3 番目の a には a_3 = 2 を代入し、計算すると、 (0-(1))*2 = -2 となり、10^9+7 を法として -2 と合同な 0 以上 10^9+6 以下の整数である、10^9+5 が答えです。

入力例 2

(a)*a+((a+(a*(a))-(a)*a+a*a))*a
10
8 6 6 4 8 1 4 3 8 9
3 4
3 9
8 4
3 7
4 0
8 9
3 6
9 0
6 8
9 4

出力例 2

552
597
642
579
282
1002
570
354
318
462

問題文

すぬけ君は、Q 日間にわたって、毎日次のようなパズルを解こうとしています。

• すぬけ君の持っている端末に、縦 H 行、横 W 列からなる格子状の盤面が毎日配信されてくる。それぞれのマスは白または黒で塗られている。ただし、i+1 日目 (1 ≤ i ≤ Q-1) に配信されてくる盤面は、i 日目に配信される盤面の上から r_i 行目で左から c_i 列目のマスの白黒が反転したものである。
• 配信されてきた盤面に対し、すぬけ君ははじめに最大 1 回、盤面の中の長方形領域を指定し、領域中の全てのマスの白黒を反転させる。
• その後、すぬけ君は 1 つの行または列を選び、その中の全てのマスの白黒を反転させるという操作を好きな回数だけ行える。
• 盤面の全てのマスを同じ色にすることが目的である。

すぬけ君は賢いので、配信されてくる盤面の中には絶対に解けないものが存在することに勘付いています。そこで、すぬけ君の代わりに、それぞれの日の盤面について、盤面の全てのマスを同じ色にする方法が存在するかどうかを判定してください。

ただし、1 日目に配信される盤面は、上から i 行目 (1 ≤ i ≤ H) で左から j 列目 (1 ≤ j ≤ W) のマスは、s_{ij} が . のとき白に、 # のとき黒に塗られています。

制約

• 1 ≤ H ≤ 2\,000
• 1 ≤ W ≤ 2\,000
• 1 ≤ Q ≤ 300\,000
• s_{ij} は . または #
• 1 ≤ r_i ≤ H (1 ≤ i ≤ Q-1)
• 1 ≤ c_i ≤ W (1 ≤ i ≤ Q-1)

入力例 1

3 4 4
...#
.###
.#.#
3 1
2 4
2 2

出力例 1

No
No
No
Yes

4 日目の盤面が、全てのマスを同じ色にする方法が存在する盤面です。

...#
..#.
##.#

この盤面からは、以下のようにして全てのマスを白にできます。

1. 盤面の右下端の 2 行 2 列の長方形領域を反転させる。
2. 上から 3 行目の全てのマスを反転させる。
3. 左から 4 列目の全てのマスを反転させる。

入力例 2

4 4 5
####
####
....
####
2 2
3 2
2 3
3 3

出力例 2

Yes
Yes
Yes
No
Yes

問題文

整数 N および M 個の整数の 3 つ組 (A_i, B_i, C_i) (1 \leq i \leq M) が与えられます。 1, 2, ..., N の置換 p であって、すべての i (1 \leq i \leq M) に対して以下の条件を満たすものの個数を 10^9 + 7 で割ったあまりを求めてください。

• 長さ N の置換をすべて辞書順に並べたとき p の A_i 個あとにあたる置換 q = [q_1, q_2, ..., q_N] が存在し、q_{B_i} = C_i である。

なお、上の条件において、A_i = 0 のとき q は p 自身であるとします。

制約

• 1 \leq N \leq 50
• 0 \leq M \leq 50
• 0 \leq A_i \leq 50 (1 \leq i \leq M)
• A_i \leq N! - 1 (1 \leq i \leq M)
• 1 \leq B_i, C_i \leq N (1 \leq i \leq M)
• i \neq j のとき、A_i \neq A_j または B_i \neq B_j または C_i \neq C_j

入力例 1

3 1
1 2 2

出力例 1

1

1, 2, 3 の置換をすべて辞書順に並べると [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] となります。 このうち条件を満たす置換は [3, 1, 2] だけです。

入力例 2

10 2
10 10 10
11 10 10

出力例 2

0

入力例 3

20 2
0 1 1
50 1 2

出力例 3

50

入力例 4

50 0

出力例 4

318608048

入力例 5

30 5
27 18 22
43 19 26
27 26 13
22 9 27
31 20 12

出力例 5

440732388

問題文

xy 平面上の点 P が格子点であるとは、点 P の x 座標および y 座標がともに整数であることをいいます。

xy 平面上の三角形 ABC について、関数 f(ABC) を三角形 ABC の内部 (周上は含まない) に存在する格子点の個数とします。

8 個の整数 X_1, Y_1, X_2, Y_2, X_3, Y_3 および W, H が与えられます。

以下の条件を満たす三角形 ABC すべてについての f(ABC) の値の和を 10^9 + 7 で割ったあまりを求めてください。

• 頂点 A の x 座標は X_1 以上 X_1 + W 未満の整数であり、y 座標は Y_1 以上 Y_1 + H 未満の整数である。
• 頂点 B の x 座標は X_2 以上 X_2 + W 未満の整数であり、y 座標は Y_2 以上 Y_2 + H 未満の整数である。
• 頂点 C の x 座標は X_3 以上 X_3 + W 未満の整数であり、y 座標は Y_3 以上 Y_3 + H 未満の整数である。

制約

• 0 \leq X_i, Y_i \leq 10^{12} (1 \leq i \leq 3)
• 1 \leq W, H \leq 40\,000
• X_1 + W \leq X_3
• X_3 + W \leq X_2
• Y_1 + H \leq Y_2
• Y_2 + H \leq Y_3

入力例 1

0 0
4 1
2 3
2 1

出力例 1

32

下の図における f(A_iB_jC_k) (i, j, k \in \{1, 2\}) の和を 10^9 + 7 で割ったあまりを求めれば良いことになります。

• f(A_1B_1C_1) = 4
• f(A_1B_1C_2) = 3
• f(A_1B_2C_1) = 6
• f(A_1B_2C_2) = 4
• f(A_2B_1C_1) = 3
• f(A_2B_1C_2) = 3
• f(A_2B_2C_1) = 5
• f(A_2B_2C_2) = 4

より、答えはこれらの和を 10^9 + 7 で割ったあまりである 32 となります。

入力例 2

1 2
100 50
50 100
10 10

出力例 2

669378679

入力例 3

100 100
10000 1000
1000 10000
99 101

出力例 3

69068642

入力例 4

0 0
1000000000000 100000000000
100000000000 1000000000000
1 1

出力例 4

24258851

入力例 5

83014267509 107013567012
918384543326 586909285896
391608717054 614178832969
40000 40000

出力例 5

569338479