# PTZSummer Day3

## A

長さ n の数列 A が与えられる
- A 内の任意の2つを削除 -> それらの xor を追加

の操作を n - 1 回行う
**必ず1回だけ**どこかのタイミングで 任意のA[i] を +1 しなければならない

最終的に残る数字の最大値を求める

======
総 XOR = X とする
操作過程で 011...11 みたいな状態を作ることができる -> 最終的な答えを X xor 111...11 にすることができる
下〇桁だけで基底作って 0 にできるかどうか

## B

木がある　葉に0～Nを書き込む　葉以外は子のmexになる　数列の書き方は$(N+1)^{葉の数}$あるがrootがiになるのはそれぞれ何通りか？

n <= 200

自分の子の内，葉っぱと葉じゃない奴を区別
葉っぱの値 : [0, 200]

1
2 3 4 5 6 7
各頂点に 葉っぱが30 個ずつくっついてる

1
|
2 + 葉っぱ * 100
|
葉っぱ * 100

1
|
2 + 葉っぱ * 100
|
3
|
葉っぱ * 100

1,1,2,4,
子を葉、次数d以上、次数d未満に分ける
d未満についてor畳み込み
d以上については下から見て行って使った子の集合を持つ？

## C

n, c が与えられる
長さ m の配列 A が良い配列である条件
- $$ A_i > 0 $$
- $$ |A_{i+1} - A_i| = 1 $$
- $$ \sum A_i = n $$

また．
$$ f(A) := \sum[A_i > A_{i+1}] $$
とする
全ての良い配列 A に対して $c^{f(A)}$ の総和を求めろ (mod 998...)

n <= 3 * 10^5, c < 998...
TL: 16sec

初項 a \sqrt n 項

$$ (a + a - \sqrt n) * (\sqrt n) / 2 <= n$$

$$ (2a \sqrt n - n) / 2 <= n$$

$$ 2a \sqrt n <= 3n$$

$$ 2a <= 3\sqrt n$$

$$ a <= 3 / 2 \sqrt n$$

長さが短い時
- prefix の max (\sqrt n)
- 現在の長さm (\sqrt n)
- 初項をaとした時 am + b の b の部分 (n)

am + b = n
a = (n - b) / m

a a+1 a a-1

4a = n
a = n/4

a a+1 a a+1

4a+2 = n
a = (n-2)/4

## D

平面上の座標が整数である全ての箇所に重みが 0 である点がある

以下のクエリを処理するデータ構造を作れ
- 1 x y d w := |X - x| < d && |Y - y| < d を満たす全ての点（X, Y） の重みを w * (d - max(|X - x|, |Y - y|)) だけ増加させる
- 2 x1 x2 y1 y2: x1 <= X <= x2, y1 <= Y <= y2 を満たす (X, Y) の点の重みの合計を (mod 2^{30}) で求めろ

TL: 18sec

## E
n 頂点の木が与えられる
以下の m 個のクエリ に答えろ

k 個の頂点 x が与えられる
あなたは x_1 から x_k まで順番に移動する．同じ頂点を複数回通るのはNG
x_i -> x_{i+1} への移動方法は2種類
- 徒歩：x_i ~ x_{i+1}のパス上全ての頂点を通る
- 舟：x_i から他の頂点を通らずにx_{i+1}にワープする

各x_iと，徒歩の際のパス上の全ての頂点について，同じ頂点を複数回通るのはNG
舟を使う回数を最小化しろ

1
|
2-3-4
|
5

1-5-2-4

葉を一つ選びます
葉のみのパスが存在する場合それを選ぶべき
そうでない場合、葉を削除してよい

1 7
| |
2-3-4-6
| |
5 8

1 - 5
5 - 7
7 - 8
8 - 3
3 - 6

3 - 4

3-3
4-4
3-4

## F

n 頂点の木と整数Kが与えられる．
頂点iの重みは A_i である．
各頂点 i について，以下の問題に答えよ

> 以下の条件を満たす頂点の部分集合の内，頂点重みの総和の最大値はいくつか
> - 頂点 i を部分集合に含む
> - 部分集合に含まれる頂点の個数は K である
> - 頂点集合からなる誘導部分グラフは連結である

N <= 40000, k <= 3000
A_i <= 500000
TL: 8sec

TL が長いので 二乗の木dpっぽく + 全方位で更新とかを基本としてどこかしら高速化できるか？

## G

n 頂点の木が与えられる
各頂点にラベル $l_u \in [0,m]$ を持たせてゲームをする．
以下の条件を満たすとき，あなたは勝利する．
- 全ての $i \in [0, m]$ に対して，$i + 1$ 以上のラベルを持つ頂点群からなる誘導部分グラフは連結である

以下のクエリに Q 回答えろ
- a_i, b_i : 頂点 a_i のラベルが b_i であるとき，他の頂点へのラベルのつけ方は $(m + 1) ^ {n - 1}$ 通りある．
- このうち，勝利条件を満たすラベルのつけ方は何種類ある？

n, q <= 10^5
m <= 30
TL: 4sec

最大値を取る頂点を根とすると，全ての辺について　親のラベル >= 子供のラベル を満たせばOK

クエリ O(NM) 解
- 頂点 a_i に接する辺の内，1辺 or 0辺を増加方向へのラベル，それ以外を減少方向へのラベルとする
- 増加方向へのラベル : 木dp をするときに，同じように増加方向へのラベルを 0 or 1 辺選択する
- 減少方向へのラベル : 木dpをするときに，その先は全て減少方向へのラベルになる

dfs(self, 今の頂点，前の頂点，前の頂点のラベル, 増加 or 減少) -> メモ化できそう
全部同じ値の時とかに重複して数えちゃう

https://yukicoder.me/problems/no/1075

## H

## I
グラフGが与えられる

グラフ H の線グラフが G となるようなグラフ H を求めろ or 存在しないことを証明しろ

ググればありそう？検索OKになったらぐぐる

https://www.nas.ewi.tudelft.nl/people/Piet/papers/JMMA2014_Iligra.pdf

線グラフの特徴
- サイクルは同じ長さのサイクルになる
- パスは長さが 1 少なくなったパスになる

## J
N個の素数が与えられる　少なくとも一つは100以下である
0以上p1*...*pN以下のうちN個の素数のいずれかで割り切れるものを列挙してソートする　隣接差分の2乗和を求めよ
## K

入力無し構築

set / xor / and / or / not / lshift / rshift

で x * y mod 2^{64} を求めろ

並列計算ができて，実行時間も小さくしないといけないみたいでやばそう

## L

## M
各行各列に1が一つずつ存在する場合badである
badなN×N Matrixであって、
サイズ(m+1)*(m+1)以上のサブ正方行列がbadでないものの数を求めよ

長さNの順列であってM+1以上N未満の長さLの連続部分列のmax-minがL-1ではない
1-Nを区切る
長さKの遷移は　K!(K>M?-1:1)　最後に個数！をかけたい
長さによる遷移の多項式をfとすると
ΣΣ[x^j]f^i * (N-j+i)! *
Kの遷移の度に最後にかける数がK-1増える？
これをfとすれば、
Σ[x^j]f^i * (N-j)!
Σf^i = 1/(1-f)　より多分いけた
上は嘘で、f_0=1,M以降は上の通りとすると
Σ[x^N]f^i i!
嘘だが？

## N