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}. \]广义 Cayley 定理
由此我们引出了广义 Cayley 定理：对于 \(n\) 个有标号的点，将它们划分成 \(k\) 个森林，使得其中 \(k\) 个关键点中没有两个在同一棵树上，的方案数是 \(kn^{n-k-1}\)。
我们已经证明过了，将这 \(k\) 个关键点连成一条链，然后照搬上面的就行了。
I. CF1762E
solution
定理一
若 \(n\) 为奇数，则答案为 \(0\)。
证明
考虑在实数域中 \(x^2\geq 0\)，但是如果你算一下奇数时所有边的乘积开个平方，这相当于 \((-1)^n\)，然而它 \(<0\)。
接下来只考虑 \(n\) 为偶数，
定理二
若树的形态固定，则边权也是固定的。
构造
考虑找到一片叶子，因为叶子只有一条边，所以直接给那条边赋权，然后砍掉叶子，继续递归。
定理三
对于一条边，如果它左边有 \(L\) 个点，右边有 \(R\) 个点：
- \(L,R\) 奇偶性相同。
- 这条边的权值为 \((-1)^L=(-1)^R\)。
证明
归纳很容易的。
其实我们考虑一棵树，我们不妨抽象一点用 \(w_u\) 表示 \(u\to fa_u\) 的边的权值，它是 \(-\prod_v w_v\)，我们换种运算：\(1+\sum_v w_v \pmod 2\)，原来是子树大小和。
定理四
对每条边分开考虑。考虑一条边在 \(1\to n\) 路径上的充要条件：\(1,n\) 各在它们两端。
故答案为 \(\sum_{1\leq i<n}(-1)^i\binom{n-2}{i-1}f(i)f(n-i)\)，其中 \(f(n)=n^{n-1}\) 是 \(n\) 个点有标号有根数的数量。
标签：盒子,17,22,sum,leq,binom,询问,2022.12,个点 From： https://www.cnblogs.com/caijianhong/p/16989009.html