# PTZSummer2022 Day5

## A

長さ N の配列 A を考える
以下の操作を1度だけやる
- l, r, k を選んで区間[l, r] にk を区間加算する

cnt_x = A の中に x が登場する回数
としたとき， max(cnt_x) の最大値はいくつか？ && 最大値を実現するような x は何種類考えられるか

マルチテストケース
$\sum N <= 500000$

## B

2 1
3 2
4 12
5 120
6 1928
7 44368
8 1394944

長さ n-1 の整数列A, B を作る
$A[i] \in [1, i]$
$B[i] \in [i+1, n]$

各 $j \in [1, n]$ について，Aのみに含まれる or B のみに含まれるを満たす必要がある

## C
長さ N の整数列が与えられる
以下の操作を繰り返す
- $2 * l \leq n ~~ \&\& ~~ a_i \gt 0 (\forall i \leq l)$ を満たす l を選ぶ
- A=$a_1,..., a_l, a_{l+1}, ..., a_{2l}, a_{2l+1},..., a_n$ を
- A=$a_l + a_{l+1}, ..., a_1 + a_{2l}, a_{2l+1},..., a_n$ にする

n = 1にできる？

## D

$d * \sin \theta$ の積分の形になる

- $\sum \sin, \sum \cos$ をもって加法定理で更新していく？
- dが変化するから無理

## E
木が与えられる
$lca(u,v) \le u \times v$ となるような unordered pair $(u,v)$ は何通りか N頂点それぞれを根にした場合について求めよ
$N \le 300000$

lca を固定して$lca(u,v) \gt u \times v$
を数え上げる

u,vを固定してlca>u*vとなるような根をどうにかする？
まず、u,vがlcaになる場合は無視できる
したがってu-vパス上にlcaがあるはず
各u-vパス上の点kについて、k>uvなら全体加算してkのu方向、v方向に-1みたいな感じになるが...
k降順　uv降順
kが来たときにその頂点用の周囲の辺をリセット
uvが来たときに全体加算と、u-vパス上に-1

## F

## G

## H
W個の縦線とH個の横線がある　これらの線を使って点や辺で交差しない二つの長方形を作る(包含はok)　何通り作り方があるか？ 998244353
$H,W \le 10^9$

$a_l \lt a_r, b_l \lt b_r$
$a_l \leq b_l \leq a_r \leq b_r$

- 4 $a_l \lt b_l \lt a_r \lt b_r$
- 3 $a_l = b_l \lt a_r \lt b_r$
- (2) $a_l = b_l \lt a_r = b_r$
- 3 $a_l \lt b_l \lt a_r = b_r$
- 3 $a_l \lt b_l = a_r \lt b_r$

## I
$N$人の人がいる
0日目に1人が病気に感染し、もう1人がワクチンを打つ。
i日目は以下のように進む。
・i日目以前に感染した人それぞれが、順番に残りの感染しておらずワクチンを打っていない人のうち一人を等確率で選び、感染させる。いない場合は何もしない。
・i日目以前にワクチンを打った人それぞれが、残りのワクチンを打っていない人二人を等確率で選び、ワクチンを打たせる。感染していた場合治る。

感染している人がいなくなるまでにかかる日数の期待値は？

最大log日になりそ～

$N \le 1.4 \times 10^7$
MOD 10^9+7

i日目のワクチン接種者 -> 3^i 人
i日目の感染者 -> [0, 2^i] 人
最大日数： $d = \log_3{N}$ ~ 15 or 16 くらい？

dp[i][j] := i 日目，感染者がj人
状態数は $d2^d$だけど遷移が$2^d$通りなので...

- 感染者の処理 $dp[i][min(n-3^i,2j)] = dp[i][j]$
- ワクチン接種者の処理
- $dp[i+1][j-k] += dp[i][j] * Comb(j,k)*Comb(n-3^{i}-j,2*3^i-k)$
- $dp[i+1][j] /= Comb(n - 3^i, 2 * 3^i)$

## J
文字列Sの連続部分文字列であって、反転したものより辞書順で大きいのは何個あるか？
$|S| \le 300000$

...x....y..(x>y)として、
←xとy→のLCPが寄与となる
x
lcp array (lm) x ..m.. y (rm)
+= m * Σi=lm..m, j=m..rm (sa[i]<sa[j] && s[sa[i]] > s[sa[j]])　片方だけだとBBST?

S 全体の反転 : T とする S ="ab", T = "ba"
S+ "_" + T の sa を求める　-> BIT で数える
- "ab_ba" : [4, 0, 1, 3] 2 個カウント

S = "abc" T = "cba"
S = "cba" T = "abc"

回文文字列を引く

## K
$N$ 頂点の根付き木があり、各頂点は値 $a_i$ を持つ。
$f(x,y)$ を頂点 $x$ からDFS(※)を初めて頂点 $y$ にたどり着くまでに訪れる頂点の値の最小値の期待値とする。yがxの部分木に含まれるようなすべてのペア$(x,y)$について、$f(x,y)$の総和を求めよ。

DFS：xから始めて訪れていない子を等確率で選んで進むことを繰り返す感じ

複数テストケース
$\sum N \le 8 \times 10^5$