問題文

広義単調増加な正整数列 (a_1,\ldots,a_N) が与えられます。

以下の条件をすべて満たす正整数の組 (i,j) が何個あるかを求めてください。

• 1 \leq i \lt j \leq N
• a_i は a_j の倍数

制約

• 2 \leq N \leq 3 \times 10^5
• 1 \leq a_1 \leq \ldots \leq a_N \leq 10^9
• 入力はすべて整数

入力例 1

3
2 2 3

出力例 1

1

(i,j)=(1,2) が条件を満たします。

入力例 2

5
1 1 1 1 1

出力例 2

10

1 \leq i \lt j \leq N を満たす整数組 (i,j) すべてが条件を満たします。

入力例 3

15
2 17 22 25 26 29 45 47 72 75 75 81 82 84 97

出力例 3

1

問題文

正整数 N,Q が与えられます。

i=1,2,\ldots,Q に対し以下の問題を解いてください。

• 項数 N、初項 a_i 、公差 d_i の等差数列から k_i 個の項を選んだとき、そのスコアを選ばれた項の積とする。\binom{N}{k_i} 通りの選び方に対するスコアの総和を (10^9+7) で割った余りを求めよ。

制約

• 1 \leq N \leq 10^9
• 1 \leq Q \leq 4000
• 0 \leq a_i,d_i \leq 10^9
• 1 \leq k_i \leq \min(4000,N)
• 入力はすべて整数

入力例 1

4 3
1 1 1
1 1 2
3 5 3

出力例 1

10
35
3318

i=1 では (1,2,3,4) から 1 個選ぶ方法に対するスコアの総和を求めます。選び方は 1,2,3,4 をそれぞれ選んだ場合の 4 通りで、スコアはそれぞれ 1,2,3,4 なので総和は 10 です。
i=2 では (1,2,3,4) から 2 個選ぶ方法に対するスコアの総和を求めます。選び方と対応するスコアは以下のようになり、総和は 35 です。

• 1,2 を選ぶ。スコアは 1 \times 2 = 2 である。
• 1,3 を選ぶ。スコアは 1 \times 3 =3 である。
• 1,4 を選ぶ。スコアは 1 \times 4 = 4 である。
• 2,3 を選ぶ。スコアは 2 \times 3 = 6 である。
• 2,4 を選ぶ。スコアは 2 \times 4 = 8 である。
• 3,4 を選ぶ。スコアは 3 \times 4 =12 である。

問題文

黒板に N 以下の正整数が 1 個ずつ書かれています。また、M 個の正整数 x_1,\ldots,x_M が与えられます。ここで、i \neq j ならば x_i と x_j は互いに素であることが保証されます。　　

あなたは次の操作を 0 回以上何度でも行えます。

• 1 以上 M 以下の整数 i とある x_i の倍数 y を選ぶ。黒板に y が書かれているならばそのうち 1 個を選び、\frac{y}{x_i} に書き換える。

操作後に黒板に書かれている整数の総和の最小値を求めてください。

制約

• 1 \leq N \leq 2 \times 10^9
• 1 \leq M \leq 300
• 1 \leq x_i \leq 2 \times 10^9
• i \neq j ならば x_i と x_j は互いに素
• 入力はすべて整数

入力例 1

10 2
2 3

出力例 1

24

書かれている整数が (1,2,3,4,5,6,7,8,9,10) の状態から以下のように操作をすると書かれている整数の総和が 24 になります。これが最小値です。

• i=1, y=2 として操作する。書かれている整数は (1,1,3,4,5,6,7,8,9,10) となる。
• i=2, y=9 として操作する。書かれている整数は (1,1,3,4,5,6,7,8,3,10) となる。
• i=2, y=3 として操作する。書かれている整数は (1,1,1,4,5,6,7,8,3,10) となる。
• i=1, y=8 として操作する。書かれている整数は (1,1,1,4,5,6,7,4,3,10) となる。
• i=1, y=10 として操作する。書かれている整数は (1,1,1,4,5,6,7,4,3,5) となる。
• i=2, y=3 として操作する。書かれている整数は (1,1,1,4,5,6,7,4,1,5) となる。
• i=2, y=99 として操作する。書かれている整数は (1,1,1,4,5,6,7,4,1,5) となる。
• i=1, y=4 として操作する。書かれている整数は (1,1,1,2,5,6,7,4,1,5) となる。
• i=1, y=2 として操作する。書かれている整数は (1,1,1,1,5,6,7,4,1,5) となる。
• i=1, y=6 として操作する。書かれている整数は (1,1,1,1,5,3,7,4,1,5) となる。
• i=2, y=3 として操作する。書かれている整数は (1,1,1,1,5,1,7,4,1,5) となる。
• i=1, y=4 として操作する。書かれている整数は (1,1,1,1,5,1,7,2,1,5) となる。
• i=1, y=2 として操作する。書かれている整数は (1,1,1,1,5,1,7,1,1,5) となる。

入力例 2

2000000000 3
20 23 7

出力例 2

1597222223653885214

問題文

正整数 K と 4 種類の英大文字 ATGC のみからなる文字列 S が与えられます。

S君とU君がS君から始めて交互に次の操作を行います。

• 後述の条件を満たしながら以下の 3 種類の操作のうち 1 つを選んで実行する。

  • S のある 1 文字を ATGC のどれか 1 文字に置換する。
  • S のある位置(先頭・末尾でもよい)にATGC のどれか 1 文字を挿入する。
  • S のある 1 文字を削除する(この操作は S が非空の時にのみ行える)。

• 条件：操作前の文字列を X、操作後の文字列を Y とした時、以下の 2 つの条件を満たす

  • Y の文字列長は K 以下
  • Y は X より辞書順で真に大きい

先に操作が出来なくなった方が負け、もう一方の人が勝ちとなります。

S君とU君が最善を尽くした場合、どちらが勝つかを判定してください。

制約

• 1 \leq K \leq 10^9
• 1 \leq |S| \leq \min(3 \times 10^5, K)
• K は整数
• S は ATGC のみからなる文字列

入力例 1

3
AC

出力例 1

S

入力例 2

1
T

出力例 2

U

入力例 3

1200
AGC

出力例 3

S

問題文

(1,2,\ldots,N) の順列 P=(p_1,p_2,\ldots,p_N) が与えられます。

P を 1 個以上の空でない連続部分列 X_1,X_2,\ldots,X_K に分割し、以下のように (m_1,m_2,\ldots,m_K) を定めました。

• i が奇数ならば m_i は X_i に含まれる値の最小値
• i が偶数ならば m_i は X_i に含まれる値の最大値

(m_1,m_2,\ldots,m_K) としてあり得るものの個数を (10^9+7) で割った余りを求めてください。

制約

• 1 \leq N \leq 3 \times 10^5
• 1 \leq p_i \leq N
• i \neq j ならば p_i \neq p_j
• 入力はすべて整数

入力例 1

3
1 2 3

出力例 1

3

P を分割する方法は 4 通りあり、それぞれに対応する (m_1,m_2,\ldots,m_K) は以下の通りです。

• (1,2,3) に分割する。\min(1,2,3)= 1 なので対応する数列は (1) である。
• (1), (2,3) に分割する。\min(1)= 1, \max(2,3)=3 なので対応する数列は (1,3) である。
• (1,2),(3) に分割する。\min(1,2)= 1, \max(3) = 3 なので対応する数列は (1, 3) である。
• (1),(2),(3) に分割する。\min(1)= 1, \max(2)=2, \min(3)=3 なので対応する数列は (1,2,3) である。

以上より、 (m_1,m_2,\ldots,m_K) としてあり得るものは (1), (1,3), (1,2,3) の 3 個です。

入力例 2

5
5 4 1 3 2

出力例 2

15

問題文

以下の条件を満たす長さ N+M の文字列 X が存在するかどうかを判定し、存在する場合は一つ示してください。

• X は N 個の 0 と M 個の 1 からなる
• X の長さ K の部分文字列はいずれも 1 をちょうど S 個含む

制約

• 1 \leq N,M \leq 3 \times 10^5
• 1 \leq S \leq K \leq N+M
• 入力はすべて整数

入力例 1

2 1 2 1

出力例 1

Yes
010

010 の長さ 2 の部分文字列は 01 と 10 であり、いずれも 1 をちょうど 1 個含みます。

入力例 2

10 10 20 2

出力例 2

No

問題文

S君は xy 平面上の (X,Y) にある畑で農業を始めることにしました。

しかし、平面上には N 頭のイノシシがいて畑を荒らそうとしています。i 番目のイノシシは (x_i,y_i) に棲んでいます。

S君が対処法を求めて役所に相談したところ、M 個の計画を提案されました。
i 番目の計画は直線 y = a_i x + b_i 上に柵を設置するというもので、実行する場合 2^{i-1} 円かかります。

畑を守るには i=1,2,\ldots,N すべてに対して、(X,Y) と (x_i,y_i) を結ぶ線分(端点含む)とある柵に対応する直線が交点を持つ必要があります。

計画を 0 個以上選んで実行し、畑を守るのに必要な金額の最小値を C 円とします。C を (10^9+7) で割った余りを求めてください。
ただし、どのように計画を選んでも畑を守ることが出来ない場合、代わりに -1 と出力してください。

制約

• 1 \leq N,M \leq 2 \times 10^5
• -10^9 \leq X,Y,x_i,y_i,a_i,b_i \leq 10^9
• (X,Y) \neq (x_i,y_i)
• 入力はすべて整数

入力例 1

3 3 1 1
2 4
3 9
-5 10
-4 8
3 -3
-7 7

出力例 1

5

1,3 番目の計画を選んで実行するのが最適で、C= 2^{1-1} + 2^{3-1} = 5 であるため、5 を (10^9+7) で割った余りである 5 が期待される出力です。

入力例 2

2 2 0 0
10 3
10 3
5 2
5 2

出力例 2

-1

同じ座標に複数のイノシシが棲んでいる場合や、(必要な金額を除いて)同じ計画が存在する場合があります。

問題文

変数 a があり、初め a=X です。
i=1,2,\ldots,N の順に次の操作をします。

• 1 以上 m_i 以下の整数を選び、c とする。そして、a を以下の条件を満たす整数 a' の最小値に置き換える。
  • a \lt a'
  • a' の二進数表記にはちょうど c 個の 1 が含まれる

操作終了後の a の最大値を求めてください。

制約

• 1 \leq N \leq 50
• 0 \leq X \leq 1000
• 1 \leq m_i \leq 10
• 入力はすべて整数

入力例 1

1 11
2

出力例 1

16

c=1 として操作をすると a = 16 に、c=2 として操作をすると a=12 となります。

入力例 2

23 1000
2 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 2 2 8 7 7 9 8

出力例 2

4294967296

オーバーフローに注意してください。