20260826

有 $N$ 名球员，编号 $0\sim N-1$，朋友关系构成一棵树，每个点度数不超过 $3$。部分球员忠诚（标记为 Y），其余不忠诚。忠诚球员可直接购买；购买不忠诚球员前，必须已购买他的一名朋友。需要恰好购买 $K$ 名球员。若一个大小为 $K$ 的集合能按某种顺序全部买下，则称可行。等价条件：其诱导子图的每个连通块都至少有一名忠诚球员。在所有可行集合中等概率随机选一个，求每名球员被选中的概率。
数据范围：$1\le K\le N\le 50$。
特殊性质 A：树是一条链且恰有一名忠诚球员；特殊性质 B：所有球员均忠诚。

在 $N\times M$ 的格点网格上，每个格点为白点 . 或黑点 #。一个字母 L 由一条水平线段和一条竖直线段组成，拐角为公共端点，水平向右延伸，竖直向上延伸，两条线段长度均为正（至少跨一条网格边），且经过的格点全为白点。合法标志包含三个两两不相交的 L（任意格点不能同时属于两个 L）。求合法标志数量。
数据范围：$2\le N,M\le 30$，答案在 signed 64-bit 内。
特殊性质 A：$M=2$；特殊性质 B：任意一行或一列中，每个由白点组成的极大连续段长度均不超过 $2$。

一个仅由小写字母组成的字符串，若每个长度为 $n$ 的连续子串中不同字符数不超过 $d$，则称为 $(d,n)$-齐次字符串（长度小于 $n$ 时自动满足）。给定字符串 $\text{seed}$，将所有满足：长度与 $\text{seed}$ 相同、字典序不小于 $\text{seed}$、且是 $(d,n)$-齐次字符串的字符串按字典序从小到大排列（编号从 $0$ 开始），求编号为 $k$ 的字符串；若不足 $k+1$ 个，输出空行。
输入格式：一行 $d\ n\ \text{seed}\ k$。
数据范围：$1\le d\le n\le 9$，$1\le |\text{seed}|\le 50$，$0\le k\le 10^{18}$。
特殊性质 A：$d=n$；特殊性质 B：$k=0$ 且 $d<n$。

有 $n$ 架无人机，初始 $(x_i,y_i,0)$，$m$ 条电缆，地面投影为连接两点的线段，初始网络连通且投影除端点外无交点。每条电缆有最大长度 $l$，若两端三维欧氏距离严格大于 $l$ 则立即断裂且不恢复。表演依次进行 $k$ 个动作，每个动作将一架无人机高度改变 $h$（$h>0$ 上升，$h<0$ 下降），$x,y$ 不变，高度始终非负。给定 $q$ 对关键无人机，对每对求它们第一次无法通过未断裂电缆通信的动作编号（从 $1$ 开始），若始终连通输出 $-1$。
多组测试数据，$T\le 400$，所有测试数据的 $n,k,q$ 之和均不超过 $10^6$，$m\le 3n$。
特殊性质 A：每个点度数 $\le 10$；特殊性质 B：电缆图是一棵树。