A. gym103428m

问有多少个长度为 $n$ 的 01 串，其中有 $m$ 个是 1，且最长连续的 1 的长度恰好是 $k$。十万。

Trick 1

容斥系数怎么算？

Trick 2

限制了这个串的长度和 $1$ 的个数，这意味着什么？插板的东西是什么？

solution

错解

明显不顾最长连续段限制答案是 $g(n,m)=\binom{n}{m}$。

然后我们令 $f_k$ 表示当最长连续的 $1$ 的长度至多为 $k$ 的方案数。做法我猜是这样的：

先猜有 $i$ 个连续段的长度飞出去了（$>k$），我们把它们的长度减掉 $k$，然后数：$g(n-ki,m-ki)$。
盲猜容斥系数为 $(-1)^i$，所以 $f_k=\sum_i (-1)^i g(n-ki,m-ki)$。
明显这位选手没有考虑到容斥原理外面还有组合数的问题。

明显不顾最长连续段限制答案是 $g(n,m)=\binom{n}{m}$。

明显一共有 $a=n-m$ 个零，相当于是将 $m$ 个小球放入 $a+1$ 个盒子里，要求每个盒子最少 $0$ 个最多 $k$ 个的方案数，我们记这个东西的答案为 $h(m,a+1,k)$，最终答案为 $h(m,a+1,k)-h(m,a+1,k-1)$。

着力解决 $h(n,m,k)$：将 $n$ 个相同的小球放入 $m$ 个互不相同的盒子里，要求每个盒子最少 $0$ 个最多 $k$ 个的方案数（变量名换了哦）

辅助 $g(n,m)$：将 $n$ 个相同的小球放入 $m$ 个互不相同的盒子里，要求每个盒子最少 $0$ 个~~最多 $k$ 个~~的方案数，明显 $g(n,m)=\binom{n+m-1}{m-1}$。
容斥。考虑钦定 $i$ 个盒子溢出了，将这些盒子的球数减去 $(k+1)$。现在数一下：$\Delta=i(k+1),ans=g(n-\Delta,m)$。
盲猜容斥系数为 $(-1)^i\binom{m}{i}$，所以 $h(n,m,k)=\sum_{0\leq i} (-1)^i\binom{m}{i}g(n-\Delta,m)$。

扩展：$H(n,m,[L,R])$ 表示将 $n$ 个相同的小球放入 $m$ 个互不相同的盒子里，要求每个盒子最少 $L$ 个最多 $R$ 个的方案数，很不幸它是 $h(n-mL,m,R-L)$。

G. AGC059C

小明有一个隐藏的排列 $p$，小红想要猜出来。

现在允许小红提问，每次提问的形式是 $a_i$ 和 $b_i$，然后小明会告诉小红谁大谁小。

小红是个老实的人，她的询问顺序已经提前被小明套出来了，即小明知道小红心里对 $n * (n-1) / 2$ 种可能询问的预期猜测顺序。

而且他也知道小红虽然老实，但不是笨蛋，如果某一次询问可以通过前面的结果推导出来，她就会跳过这个询问。

给定 $n* (n-1) / 2$ 个按顺序的提问，问有多少种排列 $p$，可以使得小红老老实实做出所有提问。

solution

第一步是强制定向：使 $a_i<b_i$。

然后是一个引理：只需要考虑三个元素的 “链”。（这个是最难的地方）

如果有一条很长的链 $a\to b\to c\to\cdots\to z$，然后询问了 $a\to z$。
你拎出前三个点 $x,y,z$，假如询问 $(x,y)$ 的时间戳是 $v_{x,y}$。
那么如果 $v_{x,z}>max\{v_{x,y},v_{y,z}\}$，则 $x,y,z$ 不合法。否则可以删掉 $y$。

于是我们很开心的取三个下标 $1\leq i<j<k\leq n$，然后大力的分讨。

结论一：一共只有 $(i,j),(j,k),(i,k)$ 有用。记按时间顺序的询问依次为 $x,y,z$。
结论二：按时间的前两个询问的顺序没啥用。
当 $z=(i,j)$ 是最后一个询问时，它生效的条件是 $p_j<p_k,p_i<p_k$ 或 $p_j>p_k,p_i>p_k$，简称 $x,y$ 同向。
当 $z=(j,k)$ 是最后一个询问时，对称，$x,y$ 同向。
当 $z=(i,k)$ 是最后一个询问时，它生效的条件是 $p_i<p_j>p_k$ 或者反过来，简称 $x,y$ 异向。

这意味着我们枚举三个点之后，会有一些形如 “我无条件地钦定某两个询问的回答要相同或者不同” 的东西，我们先不管环的问题，我们用种类并查集，拆点连一下，然后发现如果有环，就相当于是 $p_i<p_j$ 推出了 $p_i>p_j$。

最终的答案，每个连通块都有唯一的另一个与它对称，且只能二选一，所以 $2^{\text{全局连通块个数}/2}$。

H. cf1109d

problem

你尤其钟情 $a,b$ 这两个数。

对于一棵 N 个节点的树，已知所有边的长度都在 $[1, m]$ 之间，如果节点 $a$ 和 $b$ 的距离恰好为 $m$，那么你认为这棵树很好看。

问有多少种不同结构的 N 个节点的树。这里不同的定义是，点带标号时边的存在性不同或者边权不同。一百万。

prufer 序列

先辈告诉我们，一个 $n$ 个点有标号无根树与一个长为 $n-2$ 的每个数都在 $[1,n]$ 中的序列形成双射（经典错误：是序列不是排列）。

根据先辈告诉我们的定义，我们可以有这些结论：

$n$ 个点有标号无根树有 $n^{n-2}$ 种。
对于一个点，它的度数减一就是它在 prufer 序列中的出现次数。因为 $2(n-1)-n=n-2$。

solution

首先我们把 $a\to b$ 这条链拉出来，枚举这条链上有 $L$ 条边，那么有 $L-1$ 个不是 $a,b$ 的点，那么这部分的贡献：

选出这 $L-1$ 个点：$\binom{n-2}{L-1}(L-1)!$。注意，它有顺序。
给 $L$ 条边赋权：$\binom{m-1}{L-1}$。

然后这条链就可以扔掉了，缩成一个点。这时候一共有 $k=n-L>0$ 个点。

给剩下的 $k-1$ 条边赋权：$m^{k-1}$。

因为我们这个缩链操作非常奇怪所以对应的处理方式更加奇怪：枚举链的度数 $d<k$。

这 $d$ 条边每条边都可以随意连向链上的每一个点，$(L+1)^d$。

观察缩链树的 prufer 序列，其长度为 $k-2$，有 $d-1$ 个位置需要强制设为链点，剩下强制不是，就是说：

这个 prufer 序列的方案数为 $\binom{k-2}{d-1}\boxed{(k-1)}^{(k-2)-(d-1)}$。

现在我们品尝一下这个式子：请关爱每一个上下界

\[ans=\sum_{1\leq L<n}\binom{n-2}{L-1}\binom{m-1}{L-1}m^{k-1}\boxed{\sum_{1\leq d<k}(L+1)^d\binom{k-2}{d-1}(k-1)^{(k-2)-(d-1)}}. \]

可以看到当 $k=1$ 时后面框住的那一部分是 $1$（$\binom{-1}{-1}=1$），这给予了我们极大的信心。

下面开始化简框着的部分：请相信，所有数学公式都有最简单的样子

\[\begin{aligned} \boxed{\bf boxed}&=\sum_{1\leq d<k}(L+1)^d\binom{k-2}{d-1}(k-1)^{(k-2)-(d-1)}\\ &=\sum_{1\leq d<k}\binom{k-2}{d-1}(L+1)^d (k-1)^{k-d-1}\\ &=\sum_{0\leq d\leq k-2}\binom{k-2}{d}(L+1)^{d+1} (k-1)^{k-d-2}\\ &=(L+1)\sum_{0\leq d\leq k-2}\binom{k-2}{d} (L+1)^d (k-1)^{k-d-2}\\ &=(L+1)(L+k)^{k-2}=(L+1)n^{k-2} \end{aligned}\]

这里是要凑出二项式定理，为此我们不仅换了一次元还提了一个 $(L+1)$。

特判 $L=n-1$ 的情况之后，答案：

\[\binom{m-1}{n-2}(n-2)!+\sum_{1\leq L<\leq n-2}\binom{n-2}{L-1}(L-1)!\binom{m-1}{L-1}m^{k-1}(L+1)n^{k-2}. \]