A - 夏祭り会議 (Summer Festival Meeting)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

夏祭りの運営を担当するplatypusくんとMMNMMさんは，運営の監督をしてくれたDEGwerお兄さんと 3 人で会議をすることにしました．

会議は毎日行われ，合計で 10^{100} 回開かれました．
初回の会議は深夜ちょうどに 3 人は集まる予定でしたが，platypusくんは X 分，MMNMMさんは Y 分，DEGwerお兄さんは Z 分遅れてしまいました．
そこから 2 \leq i \leq 10^{100} である整数 i について， i-1 回目の会議で三人がそれぞれ遅刻した時間をを x 分, y 分, z 分とすると，
i 回目の会議では，platypusくんは y-z 分，MMNMMさんは z-x 分，DEGwerお兄さんは x-y 分遅れてきました．
（ -p 分遅れてきたことは p 分早めについたことと同値です．)

以上の情報から，platypusくん，MMNMMさん，DEGwerお兄さんの中で 誰か一人でも 、 一分でも早めにまたは遅めに到着することなく、深夜ぴったりに に集合できた会議のうち，最初の会議が何回目であったかを一つの整数で答えなさい．
ただし，そのような会議が存在しない場合は -1 を出力しなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq X \leq 60
  • 1 \leq Y \leq 60
  • 1 \leq Z \leq 60

入力

入力は以下の形式で標準入力から与えられる．

X Y Z
  • 1行目には 3 つの整数 X,Y,Z が空白区切りで書かれている． これは，初回の会議において，platypusくんは X 分，MMNMMさんは Y 分，DEGwerお兄さんは Z 分遅れたことを意味している．

出力

標準出力に， 10^{100} 回の会議の中で， 3 人のうち誰か一人でも深夜ちょうどに集合できた最初の会議が何回目であったかを一つの整数で一行で出力せよ． ただし，そのような会議がなかった場合， -1 を出力せよ．

入力例 1

1 2 1

出力例 1

2

この場合，二回目の会議ではplatypusくんは 2-1=1 分，MMNMMさんは 1-1=0 分，DEGwerお兄さんは 1-2=-1 分遅刻しました． MMNMMさんがちょうど深夜に集合できたことになりますので，答えは 2 です．

入力例 2

6 3 1

出力例 2

-1

この場合，どの会議でも3人の中で深夜ちょうどに集合できた人はいなかったため， -1 を出力します．この時，集合時間より早くついた場合は考慮せず，深夜きっかりに集合したときのみを考えることに注意しなさい．
B - 太鼓の名人 (Taiko Expert)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

今年も夏祭りが始まります！
夏祭りの開始は，太鼓の音で知らされることが伝統で決まっています．
夏祭り開始の太鼓の鳴らし方は，「最初に何回か面を打つ( D で表します)をしたあと，何回か縁を打つ( K で表します)をする」と決まっています．つまり，太鼓の鳴らし方は DDDD...DKKK...K のような文字列で表されます．
一回も面を打たなかったり，一回も縁を打たなかったりすることもあります．

今年は太鼓の名人であるMMNMMさんが太鼓を鳴らす役に抜擢されました．
MMNMMさんは本番で間違えないように太鼓の鳴らし方を紙に書いておきましたが，うっかり者のMMNMMさんは太鼓の鳴らし方を書いた紙をばらばらにして無くしてしまいました．
必死に紙を探して文字列を復旧しましたが，抜けがあったり，間違いがあるかもしれません．
MMNMMさんは復旧した文字列の中で抜けているところにとりあえず ? を入れておくことにしました．

復旧された紙の情報が長さ N の文字列 S として与えられます．
S と合致する，もともとの太鼓の鳴らし方として考えられるものは何通りあるか求めてください．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq N \leq 100
  • S の各文字は D または K または ?

入力

入力は以下の形式で標準入力から与えられる．

N
S
  • 1行目には，整数 N が書かれている．これは，文字列 S の長さが N であることを表している．
  • 2行目には，文字列 S が書かれている．これは，復旧された紙の情報が文字列 S で表されることを表している．

出力

標準出力に，もともとの太鼓の鳴らし方として考えられるものが何通りあるかを表す整数を1行で出力しなさい．

入力例 1

10
D??D?K??K?

出力例 1

2

DDDDKKKKKK と DDDDDKKKKK の2通りがありえる鳴らし方で、それ以外の鳴らし方は D??D?K??K? に合致しません。

入力例 2

4
?KD?

出力例 2

0

どのような鳴らし方も、 D を鳴らした後 K を鳴らすので、この文字列に合致する鳴らし方はありません。
C - 整数占い (Uranai Integer)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

MMNMMさんは，夏祭りの屋台で相性占いをすることにしました．
相性占いはおみくじの箱とその中に入っている整数が書かれた札で行います．
はじめに，箱の中には N 枚の札が入っており， i 番目( 1 \leq i \leq N )の札には整数 a_i が書かれています．

占いに参加する2人は，順番を決め，最初の人が箱の中にある札からランダムに(箱の中のどの1枚の札を選ぶことも同様に確からしくなるように)一枚札を選び，その札を戻さないままもう一人も同様に一枚札を選びます．
2人の相性は，「似(2)合い(1)の夫(2)婦(2)」にちなんで，2人の選んだ整数を X,Y とすると 2+XY+2X+2Y ですが，占いの神様は大きな数が扱えないので，実際の相性は 2+XY+2X+2Y の値を 10^9+7 で割ったあまりになります．
相性を視たあとは，選んだ札を戻さず，2人の相性 (を 10^9+7 で割ったあまり) が書かれた札を戻します．

相性占いの N-1 組目の参加者の相性 (を 10^9+7 で割ったあまり) の期待値を求めてください．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 10^6
  • 0 \leq a_i < 10^9+6 (i = 1, 2, ..., N)

入力

入力は以下の形式で標準入力から与えられる．

N
a_1 a_2 ... a_N
  • 1行目には，整数 N が書かれている．これは，はじめに箱の中には札が N 枚入っていることを表している．
  • 2行目には，整数 a_1, a_2, ..., a_N がこの順に空白を区切りとして書かれている．これは，はじめに箱の中に入っている札のうち i 枚目 (1 \leq i \leq N) が a_i であることを表している．

出力

標準出力に，に N-1 組目の参加者の相性 (を 10^9+7 で割ったあまり) の期待値を表す整数を1行で出力しなさい．絶対誤差が 10^{-5} 以下のとき，正答と判定される．

入力例 1

3
1 2 3

出力例 1

58.000000

例えば，1組目が (1, 3) の札を取って， 2 + 1 \times 3 + 2 \times 1 + 2 \times 3 = 13 の札を入れ，2組目が (2, 13) の札を取ると，2組目の相性は 2 + 2 \times 13 + 2 \times 2 + 2 \times 13 = 58 になります．
D - 木からパスへ (Tree--->path)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

platypusくんは，射的の景品で N 頂点からなる連結な無向木をもらいました． このままでは持ち運びにくいので，木を一つのパスにしたいと思いました． (パスとは，すべての頂点の次数が高々2の木のことです) platypusくんは以下の操作で木をパスにします．

  1. 頂点を好きなだけ追加する
  2. 木の頂点と1.で追加した頂点との間に，好きなだけ無向辺を加える (木の頂点同士，また1.で追加した頂点同士を辺で結ぶことはできない)
  3. 2.でできたグラフから，閉路がなくなるまで好きなだけ辺を削除していき，一つの連結なパスにする

以上の操作で，platypusくんは1.で追加する頂点をなるべく少なくしたいと思いました． 与えられた木を上記の操作でパスにするための最小の頂点追加数を求めるプログラムを作りなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 与えられるグラフは木である．

入力

入力は以下の形式で標準入力から与えられる．

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 1行目には整数 N が書かれている．これは，platypusくんが入手したグラフの頂点数を表している．
  • 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている．これは，グラフの i 番目の辺は頂点 u_{i} とv_{i} を結んでいることを表している．

出力

標準出力に，与えられたグラフをパスにするための最小の頂点追加数を一行で出力しなさい．

入力例 1

7
1 2
3 7
4 2
1 3
5 2
3 6

出力例 1

2

2 つの頂点を追加すればよいです． 追加した頂点を X ,Y と呼ぶと， X と 4 ， X と 5 ， Y と 5 ， Y と 6 を辺で結び，最後に 2 と 5 ， 3 と 6 を結ぶ辺をそれぞれ消すと， 6 - Y - 5 - X - 4 - 2 - 1 - 3 - 7というひとつながりのパスが残ります． 1 つの頂点追加のみでこのグラフをパスにすることはできないので，求める答えは 2 です．

入力例 2

5
1 3
3 2
2 5
5 4

出力例 2

0

与えられたグラフはすでにパスのため，答えは 0 です．

入力例 3

9
3 5
4 6
4 2
5 9
8 5
1 2
7 4
3 1

出力例 3

2
E - 石積み (Pyramid Piling)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

MMNMMさんは夏祭りに出ていた N 次元石屋さんで N 次元の小石をたくさん買いました．
MMNMMさんはこの N 次元の小石をある正の整数 s について一辺 s の N 次元空間上の三角形状に積みます．ただし，小石を一辺 s の N 次元空間上の三角形状に積むとは，

  • N 次元空間の格子点 (x_1, x_2, ... , x_N) であって， すべての i について x_i \geq 0 が成り立ち，かつ x_1 + x_2 + … + x_N < s が成り立つようなものすべてに1つずつ石を置くように石を積む

ことをいいます．
MMNMMさんは買った石で一辺 s_1 の N 次元空間上の三角形状に石がちょうど積めることがわかり，さらに一辺 s_2 の N-1 次元空間上の三角形状にもちょうど積めることがわかりました．
このとき， s_1 と s_2 (s_1 \neq s_2) としてありえる整数の組を一組出力してください．
ただし，MMNMMさんはか弱いプログラマーなので小石を 10^{100000} 個以上買うことはできず，狭い部屋に住んでいるので一辺 10^{18} 以上の三角形状に小石を積むことはできません．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 10^5
  • MMNMMさんが買う小石の数が 10^{100000} 個未満であり， s_1 と s_2 がともに 10^{18} を超えないような解が存在することが保証されている．

入力

入力は以下の形式で標準入力から与えられる．

N
  • 1行目には，整数 N が書かれている．これは，売られている小石が N 次元小石であり，MMNMMさんが N 次元および N-1 次元空間上の三角形状に小石を積んだことを表している．

出力

標準出力に，s_1 と s_2 としてありえる整数の組をこの順に空白を区切りとしてを1行に出力しなさい．
ただし，買う小石の数が 10^{100000} を， s_1 と s_2 が 10^{18} を超えてはならない．

入力例 1

2

出力例 1

10 55

一辺10の三角形状に石を並べると55個の石が必要で，これを一列に並べると一次元の三角形状になります．

入力例 2

3

出力例 2

20 55

どちらもちょうど1540個の石を使います．
F - 冪冪ゲーム (Powerful Fever!)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

MMNMMさんは屋台で賭け事をしています．
この賭け事は小さい勝負を繰り返すもので，勝ち続ける限りいくらでも続き，負けた時点で終了になります．
この賭け事には正の整数 a ， M が定まっています．
1回目の勝負に勝つと 1 点がもらえ， n 回目の勝負( n>1 )回目の勝負に勝つと， n-1 回目の勝負でもらった点数 x 点について， a^x 点がもらえます．
勝負に負けると 0 点がもらえます．
賭け事が終了したときの合計点数を M で割ったあまりが最終的なポイントとなり，ポイントに応じて景品がもらえます．
MMNMMさんは賭け事で合計 K 回の勝負をしました(つまり， K-1 回勝ちました)．MMNMMさんの最終的なポイントを求めてください．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq a \leq 10^{18}
  • 1 \leq M \leq 10^9+7 ， M は素数
  • 1 \leq K \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる．

a M K
  • 1行目には，整数 a ， M ， K がこの順に空白を区切りとして書かれている．これは，賭け事に定められている定数が a と M であり，MMNMMさんが K 回勝負をしたことを表している．

出力

標準出力に，MMNMMさんが賭け事で得たポイントを1行に出力しなさい．

入力例 1

2 19 6

出力例 1

9

1 + 2 + 2^2 + 2^{2^2} + 2^{2^{2^2}} + 0 = 1 + 2 + 4 + 16 + 65536 + 0 = 65559 で， 65559 を 19 で割ったあまりは 9 なので，MMNMMさんは9ポイントを得ることができます．

入力例 2

3 101 3

出力例 2

4

入力例 3

1333 1000000007 8691201001

出力例 3

589246632
G - 屋台衝突 (Food Stall Collision)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

夏祭りには N 種類の屋台が鳥居から神社の拝殿に通じる長さ 2N の道にかけて並んでいます． この道は 2N 個の区画に等間隔に分割されていて，鳥居から数えて k 番目の区画を区画 k と呼びます．また， i 番目の屋台を屋台 i と呼びます．

各屋台は，店を開くためにあらかじめ神社に営業許可を取った結果，今年はどの屋台もちょうど 2 つの区画を使ってよいことになりました． 具体的には，屋台 i には，区画 A_{i} と区画 B_{i} の使用許可が下りました． 整数A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} はすべて異なり，すべての i について A_{i} \lt B_{i} が成立します． 屋台 i は，神社に営業許可を出された区画 A_{i} と B_{i} を行き来する時に， A_{i} \leq p \leq B_{i} を満たすすべての整数 p について，区画 p を一時的に通過する必要があります． このような区画 p を「屋台 i の通路上に存在する」と言います．

屋台 x と屋台 y について，二つの屋台両方の通路上に存在する区画がある場合，商売するうえで支障が生じるかもしれません． そこで，神社は屋台同士の関係を把握するために，すべての x \neq y である屋台の組 x, y について，二つの屋台両方の通路上に存在する区画がある場合，頂点 x と頂点 y を無向辺で結んだ頂点数 N のグラフを作成しました． platypusくんは，夏祭りを最大限に楽しむために，裏ルートでこのグラフを入手しましたが，なんとこのグラフは連結な無向木でした． そこで，この木から元の A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} を復元しようと思いました．

この木から，元の整数の組 (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) として考えられるものは何通りあるかを答えるプログラムを作成しなさい． ただし，答えは非常に大きくなる可能性があるため， 1000000007 で割った余りを出力しなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 与えられるグラフは連結な無向木である．

入力

入力は以下の形式で標準入力から与えられる．

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 1行目には整数 N が書かれている．これは，platypusくんが入手したグラフの頂点数を表している．
  • 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている．これは，グラフの i 番目の辺は頂点 u_{i} と v_{i} を結んでいることを表している．

出力

標準出力に，与えられたグラフと同じグラフが作られるような (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) が何通り存在するかを 1000000007 で割った余りを一行で出力せよ． ただし，platypusくんの勘違いなどによって 0 通りの入力ケースも存在しうることに留意せよ．

入力例 1

3
1 2
1 3

出力例 1

8

この場合，考えられる (A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) は以下の 8 通りあります．

(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) =
(1,2,4,5,3,6)
(1,2,4,6,3,5)
(1,4,2,5,6,3)
(1,4,2,6,5,3)
(2,1,4,5,3,6)
(2,1,4,6,3,5)
(2,4,1,5,6,3)
(2,4,1,6,5,3)

すべての i について A_{i} \lt B_{i} という制約が存在することに注意しなさい．

入力例 2

7
1 2
1 3
1 4
2 5
3 6
4 7

出力例 2

0

このようなグラフができる (A_{1}, A_{2}, ..., A_{7}, B_{1}, B_{2}, ..., B_{7}) は存在しないため，求める答えは0です．