A 异或树
考虑假设我们已经确定了最高位，则可以按照最高位为 0/1 分成两类。
而最小生成树必然是两边连成一个联通块，中间再连一个边。我们可以分别算这两类贡献。
显然，最高位全是 $0$ 和最高位全是 $1$ 砍掉最高位后是一个子问题（只是少了一位），可以递归下去做。
注意 $n$ 很小，我们可以枚举一边联通块的大小（另一边就已经知道了），递归算 $ans(i,m-1)$ 。然后对于左边的所有方案和乘上右边的方案数量，对于右边的所有方案和乘上左边的方案数量，最后再乘一个组合数即可。
现在考虑中间的边的贡献。首先中间的边一定有最高位，我们直接把最高位的贡献算上（$2^{m-1}$ 乘上左右的方案数量乘上组合数）。
然后现在需要考虑的问题是，有两个联通块，分别有 $x,y$ 个点，两边可以填的数不超过 $2^m-1$，询问中间可以连的最小边大小为 $mx$ 的方案个数。
发现这个不太好求，我们可以转化成求 $\ge mx$ 的方案个数，最后前缀和即可。
我们考虑，如果 $mx$ 在最高位上有值，必然一边最高位上全是 $0$ ，一边最高位上全是 $1$ 。这个情况可以直接把最高位砍掉递归下去做。
否则，如果最高位上没有值，我们考虑把左边分成是否最高位有值的两块，右边分成是否有值的两块，于是最小值一定在最高位的 $0-0$ 中产生或者在最高位 $1-1$ 中产生。然后发现这是两个子问题，递归做即可。
考虑复杂度，前面状态数是 $O(n)$ ，前面需要枚举联通块 $O(n)$ ，处理后面的中间边复杂度 $O(n^22^m)$ 于是总复杂度大概是 $O(n^42^m)$。注意到枚举的数后面两个加起来也不会超过前面枚举的数，所以有值少 $\frac 1 {4}$ 的常数，同时注意到实际需要算的要抛开最高位，又有 $\frac 1 2$ 的常数，所以其实跑得很快。
这题调着有点恼火。。
1 | int n , m , P; |
B 密码
乱搞做法：对所有数取 $\ln$ 后类似字符串匹配做 NTT，最后 $\exp$ 回去，复杂度正确，精度很容易暴毙。可以参考 zyw 的实现。
正解做法：考虑把每一位的最大值拿出来代表这一位。不难发现最后只会失配 $O(\log_2v)$ 次。
简要证明：考虑一次失配。如果最大值不超过 $0.5$，那么次大值以下的值都不会到 $0.5$ ，会让 $v$ 缩小一半。否则，如果最大值超过了 $0.5$ ，失配后次大值以下的值也不会到 $0.5$ ，仍然让 $v$ 缩小一半。
倍增 + Hash 判断即可。复杂度 $O(n\log m\log v)$。代码很好写。
1 |
|
C 排列
如果我们设左边点表示一个位置，右边点表示一个数，连边表示这个点可以选这个数，那么可以连成一个二分图，我们相当于要问正好 $k$ 个位置完美匹配的方案数量。
大概画出来就张上面这个图这样
正好 $k$ 个位置不好整，可以二项式反演成钦定 $k$ 个位置。最后二项式反演回去即可。
考虑把 $\bmod m$ 相同的值分为一类，不难发现形成了两条链。考虑一条长度为 $n$ 的链上拿 $i$ 个匹配的方案数量，这个值是是 $\binom {n-i} i$。为啥呢，考虑用 $0$ 表示一个单点，$1$ 表示匹配了的两个点。最后一种链的匹配方案一定可以写成一个 $n-i$ 长的序列，其中有 $i$ 个 $1$ 。比如，011 这个序列对应了下面这个长度为 $5$ ，选择了 $2$ 个匹配的方案
由于对于第一张图那样的二分图相当于有两个链，我们对两个链分别整个匹配的生成函数然后乘起来就是这个二分图的拿匹配的方案数量的生成函数了。但是由于剩下的位置不是不选而是任意选，所以每一项还得乘上 $(n-i)!$。
考虑一共会有 $m-n\bmod m$ 个长度为 $\lfloor \frac n m \rfloor$ 的二分图，有 $n\bmod m$ 个长度为 $\lceil \frac n m \rceil$ 的二分图。我们把这些二分图选择 $i$ 个匹配的方案数量乘起来即可算出整个图钦定 $k$ 个位置的方案数量的生成函数。
最后二项式反演，做一次差卷积即可。代码很好写。
1 |
|