AGC005E - Sugigma: The Showdown

题意

有 $n$ 个点，$n-1$ 条红边和 $n-1$ 条蓝边分别把这些点连成一棵树

一开始第一个人在 $x$，第二个人在 $y$，第一个人先手，轮流操作

第一个人走红边，第二个人走蓝边，每次操作可以不动或走一条边。

当两个人相遇的时候游戏结束，第一个人希望最大化总步数，第二个人希望最小化，两个人绝顶聪明

问游戏能否结束，如果可以结束输出最后的步数

垃圾 TC 毁我青春

Codeforces 755G. PolandBall and Many Other Balls

题意

有 $n$ 个球编号为 $1,2,\dotsc,n$，一组可以是一个球 ${i}$ 或者是两个相邻的球 ${i,i+1}$

对于 $i=1,2,\dotsc,k$ 求 $n$ 个球划分成 $i$ 组的方案数，每个球至多在一个组内，并且可以不在任何一个组内

对 $998244353$ 取模

$n\le 10^9,k\le 2^{15}$

描述

Maximum-minimums identity

对于一个集合 $S$ 有

$$
\begin{align}
\max(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) \
\min(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \max(T)
\end{align}
$$

其中 $\max(S)$ 表示集合 $S$ 中的最大元素，$\min(S)$ 表示 $S$ 中的最小元素

证明略

在期望下也成立

$$
\begin{align}
E(\max(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \
E(\min(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\max(T))
\end{align}
$$

不会证

LOJ #2983. 「WC2019」数树

题意

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在边 $(p, q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。

• 问题 1：已知第一棵树，对于第二棵树的所有 $n^{n−2}$ 种选择方案，求问题 0 的答案之和。

• 问题 2：对于第一棵树的所有 $n^{n−2}$ 种选择方案，求问题 1 的答案之和。

对 $998244353$ 取模

BZOJ 3684: 大朋友和多叉树

题意

求包含 $s$ 个叶子，非叶子节点的孩子数目在集合 $D$ 中的有根树数量。

孩子之间有顺序，保证 $1\notin D$。

模质数 $950009857=453\times 2^{21}+1$

$s,|D|\le 10^5$

问题

应该是个挺简单的问题

对于 $k=0,1,\dotsc,m$ 求

$$
f_k=\sum_{i=1}^n a_i^k
$$

LOJ #6391. 「THUPC2018」淘米神的树 / Tommy

题意

有一棵 $n$ 个点的树，你要以一个顺序选择每个点恰好一次。

初始只有两个钦定点 $a,b$ 可以被选，一个点被选后所有的相邻点就可以被选择。

求方案数，模 $998244353$

没得去 PKUWC

来 WC 划划水。

要好好学习了。

特征多项式

设 $A$ 为给定的 $n\times n$ 矩阵，$I_n$ 为 $n\times n$ 单位矩阵，$A$ 的特征多项式定义为

$$
p(\lambda )=\det(\lambda I_{n}-A)
$$

其中 $\det$ 表示行列式。

Cayley–Hamilton theorem

根据 凯莱–哈密顿定理，$A$ 满足方程

$$
p(A)=0
$$

其中 $0$ 是零矩阵。

因此我们可以利用这个 $n$ 次的多项式 $p(A)$ 来降低 $A$ 的高次幂。